Any graph with an Euler circuit is connected.

595 Views Asked by At

So I started with defining an Euler circuit as a closed walk containing at least one edge, not repeating any edge, and ending the walk on the same vertex as it was started. Is this a full proof, showing that an Euler circuit is connected by definition?

Or is there any way that is more legitimate to prove this?

1

There are 1 best solutions below

2
On

The result is false as stated. For instance, let $G$ be a graph with vertices $v_1,v_2,v_3$, and $v_4$ and edges $e_1=\{v_1,v_2\},e_2=\{v_2,v_3\}$, and $e_3=\{v_3,v_1\}$. Then $G$ has an Eulerian circuit $v_1e_1v_2e_2v_3e_3v_1$ but is clearly not connected. An Euler circuit must include all of the edges of a graph, but there is no requirement that it traverse all of the vertices. What is true is that a graph with an Euler circuit is connected if and only if it has no isolated vertices: any walk is by definition connected, so the subgraph consisting of the edges and vertices making up the Euler circuit is connected, but there can be isolated vertices as well.