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 the6 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 rep￾resentation 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