# Euler circuit in a directed multigraph

## 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

• Delta2

andrewkirk
Homework Helper
Gold Member
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.

• mooncrater
Delta2
Homework Helper
Gold Member
• mooncrater