Characteristics of Eulerian Graph/Necessary Condition

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $G$ be a finite (undirected) graph.

Let $G$ be Eulerian.


Then $G$ is connected and each vertex of $G$ is even.


Note that the definition of graph here includes:

but does not include directed graph.


Proof

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 $G$.

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$, it follows that $v$ is also even.

$\blacksquare$


Sources