1 GraphsA set V, together with a set E of two-element subsets of V, defines a simplegraph (V,E), where the ends of an edge uu are precisely the vertices u and v.Indeed, in any simple graph we may dispense with the incidence function b byming each edge as the unordered pair of its ends. In a diagram of such aenangraph, the labels of the edges may then be omitted.SPECIAL FAMILIES OF GRAPHSCertain types of graphs play prominent roles in graph theory. A complete graphis a simple graph in which any two vertices are adjacent, an empty graph one inwhich no two vertices are adjacent (that is, one whose edge set is empty). A graphis bipartite if its vertex set can be partitioned into two subsets X and Y so thatevery edge has one end in X and one end in Y:such a partition (X,Y) is calleda bipartition of the graph, and X and Y its parts.We denote a bipartite graphG with bipartition (X,Y) by G[X, Y]. If G[X, Y] is simple and every vertex in Xis joined to everrtexinY.thG is called acomplete bipartite graph. A staris a complete bipartite graph G[X,Y] with [X] = 1 or [Y] = 1. Figure 1.2 showsdiagrams of a completegraph,a complete bipartitegraph, and a star.50(a)(6)(c)Fig. 1.2. (a) A complete graph, (b) a complete bipartite graph, and (c) a starA path is a simple graph whose vertices can be arranged in a linear sequence insuch a way that two vertices are adjacent if they are consecutive in the sequenceand are nonadjacent otherwise. Likewise, a cycle on three or more vertices is asimple graph whose vertices can be arranged in a cyclic sequenceinsuchawaythattwoare adjacent if they are consecin the sequence. and ar311nonadjacent otherwise; a cycle on one vertex consists of a single vertex with aloop, and a cycle on two vertices consists of two vertices joined by a pair of paralleledges. The length of a path or a cycle is the number of its edges. A path or cycleof length k is called a k-path or k-cycle, respectively; the path or cycle is odd oreven according to the parity of k.A 3-cycle is often called a triangle, a 4-cyclea quadrilateral, a 5-cycle a pentagon, a 6-cycle a heragon, and so on. Figure 1.3depicts a 3-path and a 5-cycle
4 1 Graphs A set V , together with a set E of two-element subsets of V , defines a simple graph (V,E), where the ends of an edge uv are precisely the vertices u and v. Indeed, in any simple graph we may dispense with the incidence function ψ by renaming each edge as the unordered pair of its ends. In a diagram of such a graph, the labels of the edges may then be omitted. Special Families of Graphs Certain types of graphs play prominent roles in graph theory. A complete graph is a simple graph in which any two vertices are adjacent, an empty graph one in which no two vertices are adjacent (that is, one whose edge set is empty). A graph is bipartite if its vertex set can be partitioned into two subsets X and Y so that every edge has one end in X and one end in Y ; such a partition (X,Y ) is called a bipartition of the graph, and X and Y its parts. We denote a bipartite graph G with bipartition (X,Y ) by G[X,Y ]. If G[X,Y ] is simple and every vertex in X is joined to every vertex in Y , then G is called a complete bipartite graph. A star is a complete bipartite graph G[X,Y ] with |X| = 1 or |Y | = 1. Figure 1.2 shows diagrams of a complete graph, a complete bipartite graph, and a star. v1 v2 v4 v3 v5 x1 x1 x2 x3 y1 y1 y2 y2 y3 y4 y3 y5 (a) (b) (c) Fig. 1.2. (a) A complete graph, (b) a complete bipartite graph, and (c) a star A path is a simple graph whose vertices can be arranged in a linear sequence in such a way that two vertices are adjacent if they are consecutive in the sequence, and are nonadjacent otherwise. Likewise, a cycle on three or more vertices is a simple graph whose vertices can be arranged in a cyclic sequence in such a way that two vertices are adjacent if they are consecutive in the sequence, and are nonadjacent otherwise; a cycle on one vertex consists of a single vertex with a loop, and a cycle on two vertices consists of two vertices joined by a pair of parallel edges. The length of a path or a cycle is the number of its edges. A path or cycle of length k is called a k-path or k-cycle, respectively; the path or cycle is odd or even according to the parity of k. A 3-cycle is often called a triangle, a 4-cycle a quadrilateral, a 5-cycle a pentagon, a 6-cycle a hexagon, and so on. Figure 1.3 depicts a 3-path and a 5-cycle
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 both
1.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
1 Graphsplanar, even though there are crossing edges in the particular drawing of G shownin Figure 1.1. The first two graphs in Figure 1.2, on the other hand, are not planar,as proved laterAlthough not all graphs are planar, every graph can be drawn on some surfaceso that its edges intersect only at their ends. Such a drawing is called an embeddingof the graph on the surface. Figure 1.2l provides an example of an embedding of agraph on the torus. Embeddings of graphs on surfaces are discussed in Chapter 3and, more thoroughly, in Chapter 10.INCIDENCE AND ADJACENCYMATRICESAlthough drawings are a convenient means of specifying graphs, they are clearlynotsuitableforstoringgraphsincomputers,orforapplyingmathematicalmethodsto study their properties.For these purposes,we consider two matrices associatedwith a graph, its incidence matrix and its adjacency matrixet G be a graph, with vertex set V and edge set E. The incidence matriG is the n × m matrix Mc := (me), where mwe is the number of times (0, 1, or 2)that vertex w and edge e are incident. Clearly, the incidence matrix is just anotherway of specifying the graph.The adiacencumgtrir of G is then xn matrixAc=(a..).where a.isthnumber ofedges joining vertices u and u, each loop counting as two edges. Incidenceand adjacency matrices of the graph G of Figure 1.1 are shown in Figure 1.5.Uu2101020V10101000u10110w001W010201201001y00010y0000000MGAFig.1.5. IrapBecause most graphs have mamore edges tlvertices,theadjacencymatrixof a graph is generally much smaller than its incidence matrix and thus requiresless storage space. When dealing with simple graphs, an even more compact rep-resentation is possible. For each vertex v, the neighbours of u are listed in someorder. A list (N(u) :ve V) of these lists is called an adjacency list of the graph.Simplegraphs areusually stored in computers as adjacency listsWhen G is a bipartite graph.as there are no edges joining pairs of verticesbelonging to the same part of its bipartition, a matrix of smaller size than the
6 1 Graphs planar, even though there are crossing edges in the particular drawing of G shown in Figure 1.1. The first two graphs in Figure 1.2, on the other hand, are not planar, as proved later. Although not all graphs are planar, every graph can be drawn on some surface so that its edges intersect only at their ends. Such a drawing is called an embedding of the graph on the surface. Figure 1.21 provides an example of an embedding of a graph on the torus. Embeddings of graphs on surfaces are discussed in Chapter 3 and, more thoroughly, in Chapter 10. Incidence and Adjacency Matrices Although drawings are a convenient means of specifying graphs, they are clearly not suitable for storing graphs in computers, or for applying mathematical methods to study their properties. For these purposes, we consider two matrices associated with a graph, its incidence matrix and its adjacency matrix. Let G be a graph, with vertex set V and edge set E. The incidence matrix of G is the n×m matrix MG := (mve), where mve is the number of times (0, 1, or 2) that vertex v and edge e are incident. Clearly, the incidence matrix is just another way of specifying the graph. The adjacency matrix of G is the n × n matrix AG := (auv), where auv is the number of edges joining vertices u and v, each loop counting as two edges. Incidence and adjacency matrices of the graph G of Figure 1.1 are shown in Figure 1.5. u v x w y a b c d e f g h abcdefgh u 12000010 v 10101000 w 00110100 x 00011111 y 00000001 uvwxy u 210 10 v 101 10 w 010 20 x 112 01 y 000 10 G M A Fig. 1.5. Incidence and adjacency matrices of a graph Because most graphs have many more edges than vertices, the adjacency matrix of a graph is generally much smaller than its incidence matrix and thus requires less storage space. When dealing with simple graphs, an even more compact representation is possible. For each vertex v, the neighbours of v are listed in some order. A list (N(v) : v ∈ V ) of these lists is called an adjacency list of the graph. Simple graphs are usually stored in computers as adjacency lists. When G is a bipartite graph, as there are no edges joining pairs of vertices belonging to the same part of its bipartition, a matrix of smaller size than the
1.1 Graphs and Their Representationadjacency matrix may be used to record the numbers of edges joining pairs ofvertices. Suppose that G[X,Y] is a bipartite graph, where X :- [r1, 2,..,,]and Y := (yi, y2,..., y.]. We define the bipartite adjacency matrir of G to be ther x s matrix Bc = (bg), where bij is the number of edges joining ri and yjVERTEX DEGREESThe degree of a vertex in a graph G, denoted by dc(u), is the number of edges ofG incident with y, each loop counting as two edges. In particular,if G is a simplegraph, dc(v) is the number of neighbours of v in G. A vertex of degree zero is calledan isolated verter. We denote by (G) and (G) the minimum and maximumdegrees of the vertices of G, and by d(G) their average degree, uev d(u). Thefollowing theorem establishes a fundamental identity relating the degrees of thevertices of a graph and the number of its edges.Theorem 1.1 For any graph G,Ed(a) = 2m(1.1)UEVProof Consider the incidence matrix M of G. The sum of the entries in the rowcorresponding to vertex u is precisely d(u). Therefore vev d(u) is just the sumof all the entries in M. But this sum is also 2m, because each of the m columnsums of M is 2,each edgehaving two endsUCorollary 1.2 In any graph, the number of vertices of odd degree is even.Proof Consider equation (1.1) modulo 2. We havemod 2) if d(u) is odd.d(v) =:(o (mod 2) if d(u) is evenThus, modulo 2, the left-hand side is congruent to the number of vertices of odddegree, and the right-hand side is zero. The number of vertices of odd degree istherefore congruent to zero modulo 2.LA graph G is k-regular if d(u) = k for all u e V; a regular graph is one thatis k-regular for some k. For instance, the complete graph on n vertices is (n - 1)regular, and the complete bipartite graph with k vertices in each part is k-regular.For k = 0, 1 and 2, k-regular graphs have very simple structures and are easilycharacterized (Exercise 1.1.5). By contrast, 3-regular graphs can be remarkablycomlexThesegaphalsorferedtoascubcgrapsplaypromnentolegraph theory. We present a number of interesting examples of such graphs in thenext section
1.1 Graphs and Their Representation 7 adjacency matrix may be used to record the numbers of edges joining pairs of vertices. Suppose that G[X,Y ] is a bipartite graph, where X := {x1,x2,...,xr} and Y := {y1,y2,...,ys}. We define the bipartite adjacency matrix of G to be the r × s matrix BG = (bij ), where bij is the number of edges joining xi and yj . Vertex Degrees The degree of a vertex v in a graph G, denoted by dG(v), is the number of edges of G incident with v, each loop counting as two edges. In particular, if G is a simple graph, dG(v) is the number of neighbours of v in G. A vertex of degree zero is called an isolated vertex. We denote by δ(G) and ∆(G) the minimum and maximum degrees of the vertices of G, and by d(G) their average degree, 1 n v∈V d(v). The following theorem establishes a fundamental identity relating the degrees of the vertices of a graph and the number of its edges. Theorem 1.1 For any graph G, v∈V d(v)=2m (1.1) Proof Consider the incidence matrix M of G. The sum of the entries in the row corresponding to vertex v is precisely d(v). Therefore v∈V d(v) is just the sum of all the entries in M. But this sum is also 2m, because each of the m column sums of M is 2, each edge having two ends. Corollary 1.2 In any graph, the number of vertices of odd degree is even. Proof Consider equation (1.1) modulo 2. We have d(v) ≡ 1 (mod 2) if d(v) is odd, 0 (mod 2) if d(v) is even. Thus, modulo 2, the left-hand side is congruent to the number of vertices of odd degree, and the right-hand side is zero. The number of vertices of odd degree is therefore congruent to zero modulo 2. A graph G is k-regular if d(v) = k for all v ∈ V ; a regular graph is one that is k-regular for some k. For instance, the complete graph on n vertices is (n − 1)- regular, and the complete bipartite graph with k vertices in each part is k-regular. For k = 0, 1 and 2, k-regular graphs have very simple structures and are easily characterized (Exercise 1.1.5). By contrast, 3-regular graphs can be remarkably complex. These graphs, also referred to as cubic graphs, play a prominent role in graph theory. We present a number of interesting examples of such graphs in the next section.
1 GraphsPROOF TECHNIQUE: COUNTING IN TWO WAYSIn proving Theorem 1.1, we used a common proof technique in combinatoricsnas countingintwoways.It consists of considering a suitablematrixand computing the sum of its entries in two different ways: firstly as the sumofitsrowsumsandseondlyasthsumfisclumnsums.Equatingthetwo quantities results in an identity. In the case of Theorem 1.1, the matrixwe considered was the incidence matrix of G. In order to prove the identity ofExercise 1.1.9a, the appropriate matrix to consider is the bipartite adjacencymatrix of the bipartite graph G[x,Y]. In both these cases, the choice of theappropriate matrix is fairly obvious. However, in some cases, making the rightchoice requires ingenuity.Note thatound on the sum of the column sums of a matrix isan upperclearly alson upper bound on the sum of its row sums (and wrice versaThemethodof counting imtwo ways may therefore be adaptedtoestablishinequalities. The proof of the following proposition llustrates this idea.Proposition 1.3 Let G[X,] be a bipartite graph without isolated verticessuch that d(r) ≥d(y) for all ryeE, wherereX and y eY. Then|X|<[Y],with equality if and only if d(r) = d(y) for all ry E E.Prossertion follows if we can find aofheamatrix with[X|rows andJY/ colunwhicheach rowssum isoneand each colusum is at mostone.Such a matrix can be obtained from the bipartite adjacency matrixBof G[X,] by dividing the row corresponding to vertex by d(), for each e X. (This is possible since d() + 0.) Because the sum of the entries of Bponding to is d(r), all row sums of the resulting matrix Bintherowcorreare equal to one. On the other hand, the sum of the entries in the column ofBcOonding to vertex y is 1/d(r), the sum being taken over all edgesry incident to y, and this sunost one because 1/d() ≤1/d(y) foreach edgey, by hypothesis, and because thereare d(y)edges incident toy.The above argument may be expressed more concisely as follows.>11[X]=Z=[Yd(y)d(a)aE-EdOeeEvEY EEEFurthermnore, if [X| - [Y], the middle inequality 1equality,implSDEing that d(r) = d(y) for all ry e E.An application of this proof technique to a problem in set theory about geometric configurations is described in Exercise 1.3.15
8 1 Graphs Proof Technique: Counting in Two Ways In proving Theorem 1.1, we used a common proof technique in combinatorics, known as counting in two ways. It consists of considering a suitable matrix and computing the sum of its entries in two different ways: firstly as the sum of its row sums, and secondly as the sum of its column sums. Equating these two quantities results in an identity. In the case of Theorem 1.1, the matrix we considered was the incidence matrix of G. In order to prove the identity of Exercise 1.1.9a, the appropriate matrix to consider is the bipartite adjacency matrix of the bipartite graph G[X,Y ]. In both these cases, the choice of the appropriate matrix is fairly obvious. However, in some cases, making the right choice requires ingenuity. Note that an upper bound on the sum of the column sums of a matrix is clearly also an upper bound on the sum of its row sums (and vice versa). The method of counting in two ways may therefore be adapted to establish inequalities. The proof of the following proposition illustrates this idea. Proposition 1.3 Let G[X,Y ] be a bipartite graph without isolated vertices such that d(x) ≥ d(y) for all xy ∈ E, where x ∈ X and y ∈ Y . Then |X|≤|Y |, with equality if and only if d(x) = d(y) for all xy ∈ E. Proof The first assertion follows if we can find a matrix with |X| rows and |Y | columns in which each row sum is one and each column sum is at most one. Such a matrix can be obtained from the bipartite adjacency matrix B of G[X,Y ] by dividing the row corresponding to vertex x by d(x), for each x ∈ X. (This is possible since d(x) = 0.) Because the sum of the entries of B in the row corresponding to x is d(x), all row sums of the resulting matrix B are equal to one. On the other hand, the sum of the entries in the column of B corresponding to vertex y is 1/d(x), the sum being taken over all edges xy incident to y, and this sum is at most one because 1/d(x) ≤ 1/d(y) for each edge xy, by hypothesis, and because there are d(y) edges incident to y. The above argument may be expressed more concisely as follows. |X| = x∈X y∈Y xy∈E 1 d(x) = x∈X y∈Y xy∈E 1 d(x) ≤ x∈X y∈Y xy∈E 1 d(y) = y∈Y x∈X xy∈E 1 d(y) = |Y | Furthermore, if |X| = |Y |, the middle inequality must be an equality, implying that d(x) = d(y) for all xy ∈ E. An application of this proof technique to a problem in set theory about geometric configurations is described in Exercise 1.3.15.