Sheet 3, no. 1
a) Show that if G is Eulerian, then its line-graph L(G) is Hamiltonian.
a) If G is Eulerian then it has an Eulerian tour, i.e. a sequence of vertices
v_1, v_2, …, v_r = v_1, such that:
for each i, v_i v_{i+1} is an edge of G;
and each edge of G appears once and only once.
Thus v_1 v_2, v_2 v_3, …, v_{r-1} v_r is a listing of the edges of G such that:
each edge has a vertex in common with the next one (and the last edge has a vertex in common with the first edge)
each each edge appears once and only once.
This is thus a Hamiltonian cycle of L(G).
b) Show that if G is Hamiltonian, then its line-graph L(G) is Hamiltonian.
b) If G is Hamiltonian, then it has a Hamiltonian cycle, i.e. a sequence of vertices
v_1, v_2, …, v_n such that:
each vertex appears once and only once
each vertex is adjacent to the next one (and the last is adjacent to the first).
Now we can visit all the edges of G in the following sequence:
Step 1. all edges of the form v_1 v_j (n > j > 2)
Step 1′. v_1 v_2
Step 2. all edges of the form v_2 v_j (j > 3)
Step 2′. v_2 v_3
Step 3. all edges of the form v_3 v_j (j > 4)
Step 3′. v_3 v_4
…
Step n_1′. v_{n-1} v_n
Step n’. v_n v_1
Note that every edge is of the form v_i v_j, for some i < j.
This edge will be be visited in step i (if j > i+1) or step i’ (if i = i+1). So every edge is visited
exactly once.
Also, all the edges in step i or i’ are adjacent because they have vertex i in common;
the edge in step i’ has vertex i+1 in common with the edges in steps i+1 and i+1′;
and the edge in step n’ has vertex 1 in common with the edges in steps 1 and 1′.
So each edge is adjacent to the next edge, thus giving us a Hamiltonian cycle in L(G).
Give examples to show that the converse of a) is false, and the converse of b) is false.
One example is actually enough.
Consider the star K_1,3 (i.e. vertices v,a,b,c and edges va,vb,vc).
This graph has no cycles, so it is not Eulerian or Hamiltonian.
However its line-graph is K_3, which is both Eulerian and Hamiltonian.
This shows that the converse of a) and b) is false.
