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.