In the notation of the previous exercise, prove that all cycles in the graph ϒ ⊕

ϒ* have even length. (A cycle is a path beginning and ending at the same vertex.)

Such a graph is said to be even. Show that all even connected graphs have a unique representation as ϒ ⊕ ϒ*. Hence prove that the number of connected even graphs having p labelled edges is (C

(2)

p + 1)/2 where C

(2)

p is defined in Exercise 3.22

(Gilbert, 1956)

3.27 In the terminology of the previous two exercises, what does C (3)
p in Exercise 3.23 correspond to?