G is Eulerian if and only if L(G) has a Hamiltonian cycle. L(G) is a line graph. When approaching this problem, I see that

the definition of L(G) is that it has E(G) as its vertex set, where two vertices in L(G) are linked by k edges if and only if the corresponding edges in G share exactly k vertices in common.

That implies that every vertex in L(G) is a bijective correspondence to every edge in G(Am I correct here)?

If the above assumption is correct, then since L(G) has a Hamiltonian cycle, it means that it uses every vertex in L(G) once. Which implies that every edge in G is also used once, which is the definition of an Eulerian graph.

I am not sure if there are more I should do for this proof, and I got a little stuck here. Please give me some help. thanks.


That implies that every vertex in $L(G)$ is a bijective correspondence to every edge in $G$ (Am I correct here)?

This is definition of line graph.

However your claim you want to prove is wrong. For example $L(K_4)$ is Hamiltonian, but $K_4$ isn't Eulerian. This happens because Hamiltonian cycle in $L(G)$ may have three or more consecutive vertices corresponding to edges of $G$ that share the same vertex, while Eulerian cycle can't have three such consecutive edges. Moreover Hamiltonian cycle problem is NP-complete in the class of line graphs, while Eulerian cycle problem is polynomially solvable for any graph.

So the truth and really obvious claim is that if graph $G$ is Eulerian then $L(G)$ is Hamiltonian.


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.