Prove that if G is hamiltonian then Line graph of G is hamiltonian too

470 Views Asked by At

Prove that if G is hamiltonian then Line graph of G is hamiltonian too

I know that we have a closed path with all vertices included then because every edge in this path is connected to two other edges then there will be a hamiltonian cycle in L(G) too and if we add the edges which are not in hamiltonian cycle L(G) is still hamiltonian

1

There are 1 best solutions below

7
On

Assume $G$ has a hamiltonian path $v_0,\dots, v_{n-1}$, where $v_{n-1}$ is adjacent to $v_0$.

For each $0\leq i \leq {n-2}$ we can consider the path $P_i$ in $L(G)$ that contains all edges in $G$ incident to $v_i$ such that the other vertex is $v_k$ with $k > i$ and such that the edges appear in decreasing order of $k$, so that the last element is always $\{v_i,v_{i+1}\}$

Since the last element of $P_i$ is $\{v_i,v_{i+1}\}$ the path $P_0,P_1,\dots, P_{n-2}$ is a path in $L(G)$ and one can check it contains every vertex in $L(G)$ exactly once. the first vertex is $\{v_0,v_{n-1}\}$ and the last vertex is $\{v_{n-2},v_{n-1}\}$, these last two vertices are adjacent in $L(G)$, so this is in fact a hamiltonian cycle of $L(G)$.