Discrete Mathematics: Elementary and Beyond

134 7. Graphs

7.2.7LetGbe a graph, and letH 1 =(V 1 ,E 1 ) andH 2 =(V 2 ,E 2 ) be two
subgraphs ofGthat are connected. Assume thatH 1 andH 2 have at least one node
in common. Form their union, i.e., the subgraphH=(V′,E′), whereV′=V 1 ∪V 2
andE′=E 1 ∪E 2. Prove thatHis connected.

7.2.8Determine the connected components of the graphs constructed in Exer-
cise 7.1.4.

7.2.9Prove that no edge ofGcan connect nodes in different connected com-
ponents.

7.2.10Prove that a nodevis a node of the connected component ofGcontain-
ing nodeuif and only ifgcontains a path connectingutov.

7.2.11Prove that a graph withnnodes and more than

n− 1

2


edges is always
connected.