0
$\begingroup$

Prove that the line graph of a Hamiltonian simple graph is Hamiltonian.

My proof

If $G$ is hamiltonian then there is a cycle that traverse all the vertices of $G$ exactly once. Any other edges of $G$ that's not part of this cycle can become chords of $G$ or placed outside the cycle.

How do I proceed from here?How do I use the definition of Hamiltonian to prove that the line graph of $G$ is also Hamiltonian?

$\endgroup$
  • $\begingroup$ Note that all edges incident to a vertex of $G$ form a clique in the line graph $L(G)$ of graph $G$. $\endgroup$ – Smylic Feb 16 '17 at 0:05
  • $\begingroup$ @Smylic Every two distinct vertices in clique are adjacent. Do you mean all clique in $L(G)$ together will form a cycle and make $L(G)$ Hamiltonian? $\endgroup$ – user59036 Feb 16 '17 at 0:25
  • $\begingroup$ I mean that for any vertex $v \in V(G)$ every edge $\{\,u, v\,\}$ not belonging to the selected Hamiltonian cycle $C$ in graph $G$ is adjacent to both edges incident to vertex $v$ and belonging to the cycle $C$. Also all such edges $\{\,u, v\,\}$ (with the same $v$) are adjacent to each other. $\endgroup$ – Smylic Feb 16 '17 at 9:33
  • $\begingroup$ @Smylic I'm more confused now, how does what you pointed out prove that $L(G)$ is Hamiltonian? $\endgroup$ – user59036 Feb 16 '17 at 10:02
0
$\begingroup$

Let $C_H = v_1v_2\ldots v_nv_1$ be Hamiltonian cycle in $G$. For each edge $\{\,v_i, v_j\,\} \in E(G)$ that doesn't belong to $C_H$ we choose one of two ends and assign this edge to the selected end. All edges from $C_H$ form a simple cycle $C$ in $L(G)$. Now we can insert all edges of $G$ assigned to $v_i$ between edges $\{\,v_{i - 1}, v_i\,\}$ and $\{\,v_i, v_{i + 1}\,\}$ in any order and get longer simple cycle $C'$, because all edges incident to $v_i$ are pairwise adjacent. Proceeding this for each vertex $v_i$ we get simple cycle $C^{(n)}$ in $L(G)$ containing all vertices of $L(G)$ (that are edges of $G$), so $C^{(n)}$ is Hamiltonian cycle in $L(G)$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.