1
$\begingroup$

I am trying to prove the following statement:

Show that a directed multi-graph having no isolated vertices has an Euler circuit iff the graph is weakly connected and $\text{deg}^{\text{in}} = \text{deg}^{\text{out}}$ for each vertex.

The problem I am having is understanding how to reduce the statement into two parts because of the "if and only if".

I came up with the following things I have to prove:

  1. If the graph has an Euler circuit then it is weakly connected
  2. If the graph has an Euler circuit then each vertex must have $\text{deg}^{\text{in}} = \text{deg}^{\text{out}}$

Is this correct? How does one reduce statements of the form $C$ iff $A$ and $B$?

Thanks for your time!

EDIT

Is splitting the problem like so, correct?

  1. If the multigraph (with no isolated vertices) has an Euler Circuit then the graph is weakly connected and $\text{deg}^{\text{in}} = \text{deg}^{\text{out}}$
  2. If the graph is weakly connected and $\text{deg}^{\text{in}} = \text{deg}^{\text{out}}$ then the multigraph (with no isolated vertices) has an Euler Circuit?
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.