Mathematics for Computer Science

11.9. Connectivity 325

a

b

c

d e

f

g h

Figure 11.16 A graph with 3 cycles:bhecb,cdec,bcdehb.

Definition 11.8.2.A graphGis said to be asubgraphof a graphHifV.G/

V.H/andE.G/E.H/.

For example, the one-edge graphGwhere

V.G/Dfg;h;ig and E.G/Dfhh—iig

is a subgraph of the graphHin Figure 11.1. On the other hand, any graph contain-

ing an edgehg—hiwill not be a subgraph ofHbecause this edge is not inE.H/.

Another example is an empty graph onnnodes, which will be a subgraph of anLn

with same set of nodes; similarly,Lnis a subgraph of Cn, and Cnis a subgraph

of Kn.

Definition 11.8.3.Forn 3 , letCnbe the graph with vertices1;:::;nand edges

h 1 — 2 i; h 2 — 3 i; :::; h.n1/—ni; hn— 1 i:

Acycle of a graph,G, is a subgraph ofGthat is isomorphic toCnfor some

n 3.

This definition formally captures the idea that cycles don’t have direction or be-

ginnings or ends.

11.9 Connectivity

Definition 11.9.1.Two vertices are connectedin a graph when there is a path that

begins at one and ends at the other. By convention, every vertex is connected to

itself by a path of length zero. Agraph is connectedwhen every pair of vertices

are connected.