Eulerian Graph
Contents |
Theorem
A finite (undirected) graph is Eulerian if and only if it is connected and each vertex is even.
Note that the definition of graph here includes:
but does not include directed graph.
Proof
Necessary Condition
First, we prove that any Eulerian graph is connected and has only even vertices.
Suppose that $G$ is Eulerian.
Then $G$ contains an Eulerian circuit, that is, a circuit that uses each vertex and passes through each edge exactly once.
Since a circuit must be connected, $G$ is connected.
Beginning at a vertex $v$, follow the Eulerian circuit through the graph.
As the circuit passes through each vertex, it uses two edges: one going to the vertex and another leaving.
Each edge is used exactly once, so each of the vertices must be even. Since the circuit must also end at $v$, so $v$ is also even.
Sufficient Condition
To prove the converse, suppose that a graph $G$ is connected and its vertices all have even degree.
If there is more than one vertex in the graph, then each vertex must have degree greater than $0$.
Begin at a vertex $v$.
From Graph with Even Vertices Partitions into Cycles, we know that $v$ will be on at least one cycle.
Since the graph is connected, there must be an edge $\left\{{v, v_1}\right\}$ for some vertex $v_1 \ne v$.
Since $v_1$ has even degree greater than $0$, there is an edge $\left\{{v_1, v_2}\right\}$.
These two edges make a trail from $v$ to $v_2$.
Continue this trail, leaving each vertex on an edge that was not previously used, until returning to $v$.
Do we need to prove that this process will always return you to $v$? May not be trivial, I believe, as it does not hold when the graph has odd vertices.
You can help ProofWiki by explaining it.
To discuss this point in more detail, feel free to use the talk page.
If you are able to explain it, then when you have done so you can remove this instance of {{Explain}} from the code.
If you would welcome a second opinion as to whether your explanation is correct, add a call to {{Proofread}} the page (see the proofread template for usage).
Call the circuit formed by this process $C_1$.
If $C_1$ covers all the edges of $G$, then the proof is complete.
Otherwise, remove all the edges that contribute to $C_1$ from the graph, leaving the graph $G_0$.
The remaining vertices are still even, and since $G$ is connected there is some vertex $u$ in both $G_0$ and $C_1$.
Repeat the same process as before, beginning at $u$.
The new circuit, $C_2$, can be added to $C_1$ by starting at $v$, moving along $C_1$ to $u$, travelling around $C_2$ back to $u$ and then along the remainder of $C_1$ back to $v$.
Repeat this process, adding each new circuit found to create a larger circuit.
Since $G$ is finite, this process must end at some point, and the resulting circuit will be an Eulerian circuit.
$\blacksquare$
Sufficient Condition - Alternative proof
Suppose that a graph $G$ is connected and its vertices all have even degree.
From Graph with Even Vertices Partitions into Cycles, we can split $G$ into a number of cycles $\mathbb S = C_1, C_2, \ldots, C_k$.
Start at any vertex $v$ on cycle $C_1$ and traverse its edges until we encounter a vertex of another cycle of $\mathbb S$, $C_2$ say.
We traverse the edges of $C_2$, and then resume traversing $C_1$ when we get back to it.
As we carry on traversing $C_1$, we interrupt our journey so as to traverse any other cycles of $\mathbb S$ in the same way we traversed $C_2$.
Eventually we get back to the beginning of $C_1$, which is vertex $v$.
Thus we have a circuit which includes $C_1$ and at least one other cycle (unless $C_1$ is the only cycle), as $G$ is connected.
If this circuit contains all the cycles $C_1, C_2, \ldots, C_k$, we have the required Eulerian circuit.
If not, then we travel round the circuit we have just generated, and (as $G$ is connected), we will encounter other cycles in $\mathbb S$. We traverse them as we come to them.
We continue this process till all the cycles have been included in the circuit.
At this stage, we have the required Eulerian circuit.
Hence $G$ is Eulerian.
$\blacksquare$
Sources
- Gary Chartrand: Introductory Graph Theory (1977): $\S 3.1$: Theorem $3.2$
