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.

0

0

0

0

0

0

0

0

0

0