Let G be a plane graph. For each vertex v of G with deg v 3, let e1, e2, . . ., ek (k 3)

Chapter 14, Problem 3

(choose chapter or problem)

Let G be a plane graph. For each vertex v of G with deg v 3, let e1, e2, . . ., ek (k 3) be the edges of G incident with v and arranged cyclically about v. Suppose that the vertex ui (of degree 2) is inserted into the edge ei (1 i k) and the edges u1u2, u2u3, . . . , uk1uk, uku1 are added and the vertex v is deleted. The resulting graph is called the cyclic subdivision graph of G (see Figure 14.39(a)). If a complete graph (rather than a cycle) is constructed on the vertices u1, u2, . . . , uk, then the resulting graph is called the complete subdivision graph of G (see Figure 14.39(b)). Prove or disprove: (a) A graph G is Hamiltonian if and only if its cyclic subdivision graph is Hamiltonian. (b) A graph G is Eulerian if and only if its complete subdivision graph is Eulerian.