Question

Exercise 3. Let Wn be the graph obtained from the cycle graph Cn by adding one new vertex which is adjacent to every vertex of Cn. Prove that for n ≥ 3, Wn does not have an Eulerian trail.

Answer 1

Note that each of the n vertices belonging to the original cycle now has degree 3 and the central vertex has degree n

As a vertex has degree 3, this means in an Eularian trial, exactly one edge is used to get into the vertex, one edge to go out. And another edge gets in. But as the degree is 3, there can't be another edge to get out of this vertex. So this vertex is either the starting point or the end point.

But as each of the must be either a starting point or an end point. Since there is exactly one starting and one end point, it is impossible that each of the vertices is a starting/ending point

Thus, an Eularian trial is impossible