Chapter 5, Problem 64E

Kissing circuits. When two circuits in a graph have no edges in common but share a common vertex v, they are said to be kissing at v.

a. For the graph shown in Fig 5-60, find a circuit kissing the circuit $A,D,C,A$ (there is only one), and find two different circuits kissing the circuit $A,B,D,A$.

b. Suppose G is a connected graph and every vertex in G is even. Explain why the following statement is true: If a circuit in G has no kissing circuits, then that circuit must be an Euler circuit.

Figure 5-60