Euler circuit in a directed multigraph

  • #1
217
18

Homework Statement


So the question is:
Show that a directed multigraph having no isolated vertices has an Euler circuit if and only if the graph is weakly connected and the in degree and out degree of each vertex are equal.


Homework Equations


Euler circuit: A circuit that has all edges of the graph, which aren't repeated and the circuit ends on the same vertex, where it started.
Weakly connected graph: A graph, whose underlying undirected graph is connected.(For digraphs only.)
In-degree: Number of incident edges,on a vertex, in a digraph.
Out-degree: Number of outgoing edges, from a vertex, in a digraph.

The Attempt at a Solution


Since there is a biconditional in the question, we can write it as
##p←→q##(←→ represents the biconditional)
Where ## p## is: A directed multigraph having no isolated vertices has an Euler circuit .
And ##q## is: The graph is weakly connected and the in degree and out degree of each vertex are equal.
So we can prove the given statement by proving:
1)##p→q##, and
2)##q→p##
The problem, I am facing is that, when we prove the 1st part, we have to show that Euler circuit in a directed multigraph is weakly connected. I am failing to see, how that is possible. If there is an Euler circuit present in the digraph, then reaching vertex to another is easily possible, moreover coming back is too, which makes the graph strongly connected.
One more thing, every strongly connected graph is also a weakly connected graph. I don't think this question is trying to trick me on that, but still, It can. All questions are evil, until solved.
Moon
 
  • Like
Likes Delta2

Answers and Replies

  • #2
andrewkirk
Science Advisor
Homework Helper
Insights Author
Gold Member
3,886
1,454
I don't think you are interpreting the question quite correctly. You are reading it as something like:
(a directed multigraph having no isolated vertices has an Euler circuit) if and only if (the graph is weakly connected and the in degree and out degree of each vertex are equal).
Whereas I think what it is saying is:
[If G is] a directed multigraph having no isolated vertices [then]
([G] has an Euler circuit) if and only if ([G]... is weakly connected and the in degree and out degree of each vertex are equal).
So you are asked to prove that:
$$DirectedMultiGraph(G)\wedge NoIsolatedVertices(G)\wedge (NumEulerCircuits(G)\geq 1) \leftrightarrow
DirectedMultiGraph(G)\wedge NoIsolatedVertices(G)\wedge WeaklyConnected(G)\wedge (\forall v\in V(G):\ InDegree(v)=OutDegree(v))$$

Also, if you can prove StronglyConnected then you have also proven WeaklyConnected since the former entails the latter (but not vice versa). The usual convention in mathematics is that Weakly-X or Partially-X is entailed by Strongly-X, Totally-X or just plain X, but not vice versa.
 
  • Like
Likes mooncrater

Related Threads on Euler circuit in a directed multigraph

  • Last Post
Replies
2
Views
2K
  • Last Post
Replies
2
Views
750
Replies
1
Views
3K
  • Last Post
Replies
11
Views
2K
Replies
6
Views
611
  • Last Post
Replies
3
Views
979
  • Last Post
Replies
9
Views
2K
  • Last Post
Replies
5
Views
1K
  • Last Post
Replies
2
Views
2K
  • Last Post
Replies
1
Views
1K
Top