Schaum's Outline of Discrete Mathematics, Third Edition (Schaum's Outlines)

CHAP. 8] GRAPH THEORY 181

8.8. Which of the graphs in Fig. 8-40 have a Hamiltonian circuit? If not, why not?

Graphs(a)and(c)have Hamiltonian circuits. (The reader should be able to easily find one of them.) However, graph

(b)has no Hamiltonian circuit. For ifαis a Hamiltonian circuit, thenαmust connect the middle vertex with the lower

right vertex, then proceed along the bottom row to the lower right vertex, then vertically to the middle right, but then is

forced back to the central vertex before visiting the remaining vertices.

8.9. Prove Theorem 8.3 (Euler):Afinite connected graphGis Eulerian if and only if each vertex has even degree.

SupposeGis Eulerian andTis a closed Eulerian trail. For any vertexvofG, the trailTenters and leavesvthe

same number of times without repeating any edge. Hencevhas even degree.

Suppose conversely that each vertex ofGhas even degree. We construct an Eulerian trail. We begin a trailT 1 at any

edgee. We extendT 1 by adding one edge after the other. IfT 1 is not closed at any step, say,T 1 begins atubut ends

atv=u, then only an odd number of the edges incident onvappear inT 1 ; hence we can extendT 1 by another edge

incident onv. Thus we can continue to extendT 1 untilT 1 returns to its initial vertexu, i.e., untilT 1 is closed. IfT 1

includes all the edges ofG, thenT 1 is our Eulerian trail.

SupposeT 1 does not include all edges ofG. Consider the graphHobtained by deleting all edges ofT 1 fromG.H

may not be connected, but each vertex ofHhas even degree sinceT 1 contains an even number of the edges incident

on any vertex. SinceGis connected, there is an edgee′ofHwhich has an endpointu′inT 1. We construct a trailT 2

inHbeginning atu′and usinge′. Since all vertices inHhave even degree, we can continue to extendT 2 inHuntil

T 2 returns tou′as pictured in Fig. 8-41. We can clearly putT 1 andT 2 together to form a larger closed trail inG.We

continue this process until all the edges ofGare used. We finally obtain an Eulerian trail, and soGis Eulerian.

Fig. 8-41

TREES, SPANNING TREES

8.10. Draw all trees with exactly six vertices.

There are six such trees which are exhibited in Fig. 8-42. The first tree has diameter 5, the next two diameter 4, the

next two diameter 3, and the last one diameter 2. Any other tree with 6 nodes is isormorphic to one of these trees.

Fig. 8-42

8.11. Find all spanning trees of the graphGshown in Fig. 8-43(a).

There are eight such spanning trees as shown in Fig. 8-43(b). Each spanning tree must have 4− 1 =3 edges sinceG

has four vertices. Thus each tree can be obtained by deleting two of the five edges ofG. This can be done in 10 ways,