Subscribe to the weekly news from TrueShelf


Hamiltonicity of Line Graphs

Let \(G=(V,E)\) be a simple undirected graph. The line graph \(L(G)\) of \(G\) is defined as follows:

Each vertex in \(L(G)\) corresponds to an edge in \(G\), and two vertices are connected by an edge in \(L(G)\) only if the corresponding edges in \(G\) are adjacent i.e., they share an end point.

  1. Prove that if \(G\) has a Hamiltonian cycle, then \(L(G)\) also has a Hamiltonian cycle.

  2. Prove that the converse of (1) is not true i.e., give an example of a graph \(G\) such that \(G\) does not have a Hamiltonian cycle but \(L(G)\) does.

Related Content