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^{\prime }$)

2. The next edge must share a vertex with $e$ i.e. have an edge in $G^{\prime }$

3. As every edge is visited and the euler path is closed, every vertex in $G^{\prime }$ is visited and the path is closed. That is the definition of an hamiltonian graph.

G' is eulerian

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

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

$⟹d(e),e\in E$ $even⟹G^{\prime }$ is eulerian