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.
Best Answer
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.