Show that the line graph of any quasi-cyclic graph contains a Hamiltonian cycle.

Question

The definition I have been given for a quasi-cyclic graph is as follows: a graph $G=(V, E)$ is quasi-cyclic if $1)$ it contains a unique cycle $C=(V(C), E(C))$ and $2)$ for each edge $xy$ in $E$ at least one of the vertices $x, y$ is contained in $V(C)$ the vertex set of $C$.

I really don't know how to approach this but I have been given that the line graph of a quasi cyclic graph is a cyclic sequence of cliques of size at least 2, and that every clique or size larger than 3 contains a Hamiltonian cycle.

Any help with a proof would be much appreciated as I've been stuck on this for ages!

Answer 1

Here is an example of a quasi-cyclic graph together with its dual:

As the quasi-cyclic graph, $G$ only has one cycle $C$, the dual of that circle $C$ is also a cycle $C'$. Pick a vertex on $C$, all edges connected to it form the vertexes of a complete graph on the dual. Any complete graph with more than three vertexes has a Hamiltonian cycle: pick any vertex and move to a vertex unvisited before in the complete graph until you can no longer do it and comes back to the original vertex. You can do this traversing business because every vertex has a degree of at least 2.

Answer 2

Essentially, we need to show that we can list all edges of the original graph so that successive edges are incident and the first and last edges on the list are the same. Let $v_1,\dots,v_n$ be the vertices of $C$ and let $v_0=v_n$. Now let $e_k=v_{k-1}v_k$ for $k=1,\dots,n$, and let $e_0=e_n$. Start with the edges of the cycle $C$ in order, $e_0e_1\dots e_n$, then, for each $k=1,\dots,n$, insert between $e_{k-1}$ and $e_k$ all other edges incident with $v_{k-1}$ in any order. This produces a Hamilton cycle of the line graph.