# Homework Help: Euler circuit in a directed multigraph

Tags:
1. Jun 19, 2016

### mooncrater

1. The problem statement, all variables and given/known data
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.

2. Relevant 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.

3. 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

2. Jun 20, 2016

### andrewkirk

I don't think you are interpreting the question quite correctly. You are reading it as something like:
Whereas I think what it is saying is:
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.

3. Jun 20, 2016