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