Prove: if G has a closed hamilton walk then L(G) has one too.

Question

L(G): L Line Graph If G is a graph with e ≠ 0 then the line graph of G, denoted “L(G)”, is the graph having one vertex corresponding to each edge of G and such that two vertices of L(G) are joined by an edge whenever the corresponding edges of G share a vertex.

This question is from Richard J. Trudeau - Introduction to Graph Theory-Dover Publications p.234

Answer 1

Let $G$ be our graph, and $C: v_1, v_2, \dots, v_n$ its Hamiltonian cycle. Denote by $x_i$ the edge $v_iv_{i+1}$, setting $x_n = v_nv_1$. So the edges $x_1, x_2, \dots, x_n$ are the edges of our hamiltonian cycle $C$.

We will need two important facts:

1. If $\{e_1, e_2, \dots, e_k\}$ are the $k$ edges incident to a vertex $v_i$ in $G$, then $\{e_1, e_2, \dots, e_k\}$, considered as a set of vertices in $L(G)$, forms a clique in $L(G)$. We will call this clique $K_i$.
2. Given adjacent vertices $v_i$ and $v_{i+1}$ in $G$, the two cliques $K_i$ and $K_{i+1}$ share exactly the vertex $x_i$ in $L(G)$.

With these facts, we can construct our Hamiltonian cycle in $L(G)$. Let $S_1 = \emptyset$. Since $K_1$ is a clique containing both $x_n$ and $x_1$, there is a path $P_1: x_n, \dots, x_1$ in $K_1$ that starts at $x_n$, ends at $x_1$, and contains every vertex of $K_1$.

Now update $S_2 = S_1 \cup V(K_1)$. The subgraph $K_2 - S_2$ of $L(G)$ is a clique containing $x_1$ and $x_2$. Thus there is a path $P_2 : x_1, \dots, x_2$ in $K_2 - S_2$ that contains every vertex of $K_2 - S_2$.

We repeat this process, setting $S_{i+1} = S_{i} \cup V(K_{i})$, and obtaining a path $P_{i+1}: x_i, \dots, x_{i+1}$ that contains all the not yet used vertices of $K_{i+1}$, for each $i < n$.

Since every edge is incident to some vertex $v_i$ of $C$, the paths $P_1, P_2, \dots, P_n$ contain every vertex of $L(G)$. Further, by using the sets $S_i$ to track which edges we already used, we have made sure the paths do not have common vertices other than the end-points. So laying the paths 'end to end' yields a Hamiltonian cycle $P_1 \cup P_2 \cup ... \cup P_n$ of $L(G)$.