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

CHAP. 8] GRAPH THEORY 183

(iv) implies(i) Since adding any edgee={x, y}toGproduces a cycle, the verticesxandymust already be connected

inG. HenceGis connected and by hypothesisGis cycle-free; that is,Gis a tree.

Fig. 8-45

8.14. Prove Theorem 8.6: LetGbe a finite graph withn ≥1 vertices. Then the following are equivalent.

(i)Gis a tree, (ii)Gis a cycle-free and hasn−1 edges, (iii)Gis connected and hasn−1 edges.

The proof is by induction onn. The theorem is certainly true for the graph with only one vertex and hence no edges.

That is, the theorem holds forn=1. We now assume thatn>1 and that the theorem holds for graphs with less than

nvertices.

(i) implies(ii) SupposeGis a tree. ThenGis cycle-free, so we only need to show thatGhasn−1 edges. By Problem

8.38,Ghas a vertex of degree 1. Deleting this vertex and its edge, we obtain a treeTwhich hasn−1 vertices.

The theorem holds forT,soThasn−2 edges. HenceGhasn−1 edges.

(ii) implies(iii) SupposeGis cycle-free and hasn−1 edges. We only need show thatGis connected. SupposeGis

disconnected and haskcomponents,T 1 ,...,Tk, which are trees since each is connected and cycle-free. SayTihas

nivertices. Noteni<n. Hence the theorem holds forTi,soTihasni−1 edges. Thus

n=n 1 +n 2 +···+nk

and

n− 1 =(n 1 − 1 )+(n 2 − 1 )+···+(nk− 1 )=n 1 +n 2 +···+nk−k=n−k

Hencek=1. But this contradicts the assumption thatGis disconnected and hask>1 components. HenceGis

connected.

(iii) implies(i) SupposeGis connected and hasn−1 edges. We only need to show thatGis cycle-free. SupposeG

has a cycle containing an edgee. Deletingewe obtain the graphH=G−ewhich is also connected. ButHhas

nvertices andn−2 edges, and this contradicts Problem 8.39. ThusGis cycle-free and hence is a tree.

PLANAR GRAPHS

8.15. Draw a planar representation, if possible, of the graphs (a), (b), and (c) in Fig. 8-46.

Fig. 8-46