1
$\begingroup$

Background

A connected graph has an Eulerian circuit if every vertex has even degree.

I am thinking about a certain classification of connected graphs where, for a connected graph $G$, every cut splits (intersects) an even number of edges.

For example, while the following graph does not have an Eulerian circuit, the displayed cut 'splits an even number of edges':

Graph cut

Claim: A connected graph $G$ has an Eulerian circuit iff every cut of $G$ splits an even number of edges.

Proof attempt:

($\rightarrow$) If $G$ has an Eulerian circuit then ... ?

($\leftarrow$) Suppose every cut splits an even number of edges. Then we can make a cut around each individual vertex that will split an even number of edges. Hence the degree of each vertex is even. Therefore $G$ has an Eulerian circuit.

I'm lost in the forwards direction of the proof. Any hint would be appreciated.

$\endgroup$
0

2 Answers 2

3
$\begingroup$

Given any cut and any Eulerian circuit, the circuit has to cross from one side of the cut to another an even number of times, since it starts and ends on the same side of the cut.

Since the Eulerian circuit takes each edge once, the number of edges split by the cut is even.

$\endgroup$
0
$\begingroup$

Given: $\forall v \in V: \textrm{deg}(v) \equiv 0 \pmod 2$. Partition $V$ into $S$ and $T$. We desire to show that the number of edges split by the cut is even.

By induction on the size of $T$.

Base case: when $|T| = 0$, there are $0$ edges split by the cut, which is even.

Inductive step: if it holds for all $|T| = n$, transfer vertex $u$ from $S$ to $T$. Since $u$ has an even number of edges in total, its edges to $S$ and its edges to $T$ have the same parity, so adding the edges $u-S$ to the cut and removing the edges $s-T$ from the cut doesn't change the parity of the number of edges split by the cut.

QED.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .