1.1 Graphs and Their Representation(a)(b)Fig. 1.3. (a) A path of length three, and (b) a cycle of length fiveAgraphisaected if, for every partition of its vertex sesets X and Y, there is an edge with one end in X and one end in Y; otherwise thegraph is disconnected. In other words, a graph is disconnected if its vertex set canbe partitioned into two nonempty subsets X and Y so that no edge has one endin X and one end in Y.(It is instructive to compare this definition with that ofabipartitegraph.)Examples of connected and disconnectedgraphsaredisplayedinFigure1.4(a)(6)Fig. 1.4. (a) A connected graph, and (b) a disconnected graphAs observed earlier,examples ofgraphs abound in the real world.Graphsalsarise naturally in the study of other mathematical structures such as polyhedra,lattices, and groups These graphs are generally defined by means of an adjacencyrule, prescribing which unordered pairs of vertices are edges and which are not. Anumber of such examples are given in the exercises at the end of this section andin Section 1.3.For the sakeof clarity,weobservecertain conventions in representing graphs by we do not allow an edge to intersect itself, nor let an edge pass throughdiapraa vertex that is nan end of the edge; clearly, this is always possible. However intersect at a point that does not correspond to a vertex, as in thetwo edgesdrawings of the first two graphs in Figure 1.2. A graph which can be drawn in theplanein such a waythat edges meet only atpoints correspondingtotheircommonends is called a planar graph, and such a drawing is called a planar embeddingof the graph. For instance, the graphs G and H of Examples 1 and 2 are both1.1 Graphs and Their Representation 5 u1 u2 u3 u4 v1 v2 v4 v3 v5 (a) (b) Fig. 1.3. (a) A path of length three, and (b) a cycle of length five A graph is connected if, for every partition of its vertex set into two nonempty sets X and Y , there is an edge with one end in X and one end in Y ; otherwise the graph is disconnected. In other words, a graph is disconnected if its vertex set can be partitioned into two nonempty subsets X and Y so that no edge has one end in X and one end in Y . (It is instructive to compare this definition with that of a bipartite graph.) Examples of connected and disconnected graphs are displayed in Figure 1.4. 1 1 2 2 3 3 4 4 5 5 6 6 7 7 (a) (b) Fig. 1.4. (a) A connected graph, and (b) a disconnected graph As observed earlier, examples of graphs abound in the real world. Graphs also arise naturally in the study of other mathematical structures such as polyhedra, lattices, and groups. These graphs are generally defined by means of an adjacency rule, prescribing which unordered pairs of vertices are edges and which are not. A number of such examples are given in the exercises at the end of this section and in Section 1.3. For the sake of clarity, we observe certain conventions in representing graphs by diagrams: we do not allow an edge to intersect itself, nor let an edge pass through a vertex that is not an end of the edge; clearly, this is always possible. However, two edges may intersect at a point that does not correspond to a vertex, as in the drawings of the first two graphs in Figure 1.2. A graph which can be drawn in the plane in such a way that edges meet only at points corresponding to their common ends is called a planar graph, and such a drawing is called a planar embedding of the graph. For instance, the graphs G and H of Examples 1 and 2 are both