TU Wien:Diskrete Mathematik für Informatik UE (Gittenberger)/Übungen WS13/Beispiel 28

For a simple and undirected graph G we define the line graph G' and (e, f ) ∈ E(G') if and only if the edges e and f share a vertex. Prove that the line graph of an Eulerian graph is Eulerian and Hamiltonian!

Solution

G' is hamiltonian

1. Take an edge $e$ from the euler path of $G$. (This is a vertex in $G'$)

2. The next edge must share a vertex with $e$ i.e. have an edge in $G'$

3. As every edge is visited and the euler path is closed, every vertex in $G'$ is visited and the path is closed. That is the definition of an hamiltonian graph.

G' is eulerian

$G$ $eulerian\implies \forall v:d(v)=2\cdot n,n\in \mathbb {N}$

$\implies \forall v:|\Gamma (v)|$ $even$ i.e. an even number of edges share this vertex

$\implies d(e),e\in E$ $even\implies G'$ is eulerian