辅导案例-MAT3043

MAT3043: GRAPHS AND NETWORKS Lectures Spring Semester 2019/20 Contents 1 Graphs: basic properties and particular types 3 1.1 Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.1.1 Basic definitions . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.1.2 Some specific graphs . . . . . . . . . . . . . . . . . . . . . . . 4 1.1.3 Degree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.1.4 Subgraphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.1.5 Isomorphic graphs . . . . . . . . . . . . . . . . . . . . . . . . 8 1.1.6 Walks, trails, paths and cycles . . . . . . . . . . . . . . . . . . 8 1.1.7 Complement . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 1.1.8 Bipartite graphs . . . . . . . . . . . . . . . . . . . . . . . . . . 10 1.1.9 Degree sequences and the Havel-Hakimi condition . . . . . . . 12 1.1.10 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 1.2 Connectedness of graphs . . . . . . . . . . . . . . . . . . . . . . . . . 16 1.2.1 Definition of connectedness . . . . . . . . . . . . . . . . . . . . 16 1.2.2 Separating and disconnecting sets . . . . . . . . . . . . . . . . 17 1.2.3 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 1.3 Eulerian and Hamiltonian graphs . . . . . . . . . . . . . . . . . . . . 22 1.3.1 Eulerian graphs . . . . . . . . . . . . . . . . . . . . . . . . . . 22 1.3.2 Hamiltonian graphs . . . . . . . . . . . . . . . . . . . . . . . . 24 1.3.3 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 1.4 Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 1.4.1 Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 1.4.2 Prufer sequences . . . . . . . . . . . . . . . . . . . . . . . . . 30 1 1.4.3 Spanning trees and forests . . . . . . . . . . . . . . . . . . . . 33 1.4.4 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 2 Planar graphs, colouring, matching and flows 37 2.1 Planar graphs and dual graphs . . . . . . . . . . . . . . . . . . . . . . 37 2.1.1 Planar graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 2.1.2 Kuratowski’s theorem . . . . . . . . . . . . . . . . . . . . . . 40 2.1.3 Geometric dual . . . . . . . . . . . . . . . . . . . . . . . . . . 41 2.1.4 Maximal planar graphs . . . . . . . . . . . . . . . . . . . . . . 44 2.1.5 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 2.2 Graph colourings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 2.2.1 The chromatic number and the greedy algorithm . . . . . . . 47 2.2.2 The five and four colour theorems . . . . . . . . . . . . . . . . 48 2.2.3 Maps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 2.2.4 Chromatic polynomials . . . . . . . . . . . . . . . . . . . . . . 51 2.2.5 Chromatic index and Vizing’s theorem . . . . . . . . . . . . . 54 2.2.6 Ko¨nig’s theorem . . . . . . . . . . . . . . . . . . . . . . . . . . 55 2.2.7 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 2.3 Matchings and flows . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 2.3.1 Menger’s theorem . . . . . . . . . . . . . . . . . . . . . . . . . 59 2.3.2 Hall’s theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 2.3.3 Transversals . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61 2.3.4 Networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61 2.3.5 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64 3 Graphs and matrices 65 3.1 Adjacency matrix . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65 3.2 Incidence matrix . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70 3.3 Degree and Laplacian matrices . . . . . . . . . . . . . . . . . . . . . . 72 3.4 Matrix tree theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . 73 3.5 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77 2 Chapter 1 Graphs: basic properties and particular types 1.1 Graphs 1.1.1 Basic definitions Definition 1.1 A graph G consists of a non-empty set V (G) of vertices (or nodes) and a set E(G) of edges, such that each edge joins a vertex to a vertex. V (G) is the vertex set and E(G) is the edge set of G. The order of G is |V (G)|, the number of vertices. We shall consider only finite graphs, i.e. V (G) and E(G) will be finite sets. A graph can be represented by a diagram called a drawing of the graph, in which elements of V (G) and E(G) are shown as points and lines respectively. The vertices will usually be denoted by lower-case letters and the edges by pairs of letters, such as uv, which at present are unordered so vu = uv. We can also use a single letter for an edge, e.g. e = uv. Position and distance do not matter; only the connections between the vertices and edges are important. Thus the same graph can have several different drawings. The following all represent the same graph, having four vertices with a single edge joining each pair: 3 Definition 1.2 If e = uv is an edge in a graph, we say that e and u are incident, as are e and v. The vertices u and v are then adjacent, and each is a neighbour of the other. Edges are adjacent if they are incident to the same point. A set of vertices (or edges) is independent if no two of them are adjacent. If edges e1, e2 join the same vertices u and v, they are parallel or multiple edges. A loop is an edge of the form vv, i.e. it joins a vertex to itself. A graph is a simple graph if it has no multiple edges or loops, and a multigraph otherwise. A directed graph or digraph is a graph in which a direction is assigned to each edge; the edges are then called arcs. The direction is indicated by an arrow. Example This graph G is not a simple graph. V (G) = {v1, v2, v3, v4}, E(G) = {e1, e2, . . . , e10}. All pairs of vertices are adjacent except for v1 and v4. e3 and e4 are adjacent edges. v1 is incident to e1, e2, e3, e4. e1 is a loop at v1. e2, e3 are parallel edges. 1.1.2 Some specific graphs Definition 1.3 The null graph Nn is the graph with n vertices and no edges. The complete graph Kn is the simple graph with n vertices and an edge joining every pair of distinct vertices. The path graph Pn is the simple graph which can be represented by a straight line connecting n points. For n ≥ 3, the cycle graph Cn is the simple graph which can be represented by the vertices and edges of an n-sided polygon. C1 is a loop, C2 is a pair of parallel edges. For n ≥ 4, the wheel Wn is the graph formed by joining each vertex of Cn−1 to one more vertex. The complete graphs K1(= N1), K2(= P2), K3(= C3), K4, K5. 4 The null graph N6, cycle graph C6, wheel graph W6 and path graph P6: It is clear that the number of edges in Kn is ( n 2 ) , which equals n(n− 1) 2 . This is therefore the greatest possible number of edges in any simple graph with n vertices. A particular set of graphs can be obtained from the five regular three-dimensional figures known as the Platonic solids: the tetrahedron, cube, octahedron, icosahe- dron and dodecahedron. These Platonic graphs preserve the incidence of vertices and edges in the solids. The faces of the solid are represented by the regions bounded by edges, except for one face which corresponds to the infinite exterior region of the graph. The right-hand diagram shows how the graph of the cube is obtained by projecting the vertices and edges onto a plane. 1.1.3 Degree Definition 1.4 Let v be a vertex of a graph G. The degree (or local degree or valency) of v, denoted by d(v) or deg(v), is the number of edges which are incident to v, except that a loop at v contributes 2 to d(v). δ(G) and ∆(G) denote the minimum and maximum degree, respectively, of any vertex in G. An isolated vertex is a vertex of degree 0. An end vertex or terminal vertex or pendant vertex is a vertex of degree 1. A regular graph is a graph in which every vertex has the same degree. If this degree is r then the graph is r-regular, or regular of degree r. A 3-regular graph is cubic. 5 Examples (i) In Example 1.1.1, d(v1) = 5, d(v2) = 6, d(v3
) = 6, d(v4) = 3. Thus δ(G) = 3 and ∆(G) = 6. There are no isolated or end vertices. G is not regular. (ii) In Nn, all vertices are isolated. Nn is regular of degree 0, for each n ∈ N. (iii) Kn can be drawn as a regular n-sided polygon with all its diagonals, but the points where these diagonals cross are not vertices of the graph. In Kn, every vertex has degree n− 1, so Kn is (n− 1)-regular. K2 has two end vertices. (iv) The graph shown here is called the Petersen graph. It is cubic (3-regular), as each of its 10 vertices has degree 3. It has 15 edges. Note that some edges cross in the diagram at points which are not vertices. We can think of these lines as being on different horizontal levels, so they do not intersect at all. Proposition 1.1 (i) Let G be a graph with m edges. Then ∑ v∈V (G) d(v) = 2m. (ii) The number of vertices of odd degree in any graph is even. Proof (i) In calculating the sum of the degrees, each edge uv is counted in both d(u) and d(v). Also by definition a loop is counted twice, so the sum of the degrees is twice the number of edges. (ii) Suppose there are p odd-degree vertices and q even-degree vertices. Then the sum of the degrees is the sum of p odd numbers and q even numbers. By (i) this sum is even, so p must be even. The above result is attributed to Euler. Part (i) is often called the handshaking lemma, since it shows that if a number of people all shake hands with one another then the total number of hands shaken is even. 1.1.4 Subgraphs Definition 1.5 A subgraph of a graph G is a graph whose vertex and edge sets are subsets of V (G) and E(G) respectively. A spanning subgraph of G is a subgraph H such that V (H) = V (G). An induced subgraph of G is a subgraph H which contains every edge of G that is incident only to vertices in V (H). 6 Let S be a subset of V (G). Then G− S is the graph obtained from G by deleting all the vertices in S and all edges incident to them. G − v is obtained by deleting a single vertex v and all its incident edges. Let F be a subset of E(G). Then G− F is the graph obtained from G by deleting all the edges in F . G−e is obtained by deleting a single edge e. No vertices are deleted. G \ e is the graph obtained by contracting the edge e, i.e. deleting e and replacing its endpoints u and v with a single vertex incident to all edges that were incident to u or v in G. Given graphs G1 and G2, their union G1 ∪G2 is the graph which has vertex set V (G1) ∪ V (G2) and edge set E(G1) ∪ E(G2). Note that contracting an edge can introduce multiple edges. These may be removed if a simple graph is required. Examples Here are some subgraphs of the graph G in Example 1.1.1 Contraction of the edge e to give a multi- graph or a simple graph. 7 1.1.5 Isomorphic graphs Definition 1.6 Two graphs G1, G2 are isomorphic (written G1 ∼= G2) if there is a bijection φ : V (G1) → V (G2) such that for any u, v ∈ V (G1), the number of edges joining u and v in G1 equals the number of edges joining φ(u) and φ(v) in G2. The map φ is then a graph isomorphism. In particular, an isomorphism must preserve essential properties of a graph such as the number of vertices of a given degree and the number of loops (if any). The three graphs on Page 1 are isomorphic, as they are different drawings of the same graph. For unlabelled graphs, ‘isomorphic’ can be taken to mean ‘the same’. However, we can also consider labelled graphs, in which a name is assigned to each vertex. Regarded as labelled graphs, the following are isomorphic but only the first two are the same. An isomorphism from either of the first two graphs to the third is given (not uniquely) by A 7→ D, B 7→ B, C 7→ C, D 7→ A. The following diagram shows eight distinct labelled simple graphs with three vertices 1, 2, 3. If we were considering unlabelled graphs, only four of these would be distinct: N3, P2 ∪N1, P3, C3. 1.1.6 Walks, trails, paths and cycles Definition 1.7 A walk (or edge sequence) in a graph is a finite ordered list of edges e1, e2, . . . , er in which consecutive edges are adjacent or the same. It can also be denoted by v0v1v2 · · · vr where v0, v1, etc, are the vertices in the order in which they are encountered. v0 is the initial vertex and vr is the final vertex of the walk, which has length r (the number of edges). A trail is a walk in which all the edges are distinct. A path is a trail in which all the vertices are distinct (an open path), or all distinct except for the initial and final vertex (a closed path, also called a cycle or circuit). 8 The distance `(u, v) between vertices u and v is the number of edges in the shortest path between u and v. A connected graph is a graph in which there is a walk between any two vertices. Cycles of length 1, 2 and 3 are respectively a loop, a pair of parallel edges and a triangle. Example In Example 1.1.1, e2, e3, e4, e6, e6, e9, e10 is a walk of length 7 from v1 to v3. e1, e3, e6, e7, e8, e10, e4, e2 is a trail of length 8 from v1 to v2. e2, e8, e9, e4 is a closed path from v1 to v1. It is a cycle of length 4. `(v1, v2) = 1, `(v1, v4) = 2. Proposition 1.2 Every simple graph G contains a path of length δ(G). Proof Let v0 · · · vr be a path of maximal length r in G. Every vertex adjacent to vr must lie on this path, otherwise the path could be extended to such a vertex, so r ≥ d(vr) ≥ δ(G). Hence this maximal-length path, or a path contained in it, has length δ(G). Proposition 1.3 Let G be a graph with no isolated or terminal vertices. Then G contains a cycle. If G is simple then there is a cycle of length at least δ(G) + 1. Proof The existence of a cycle is clear if G has any loops or multiple edges. Suppose G is simple. Let v0 · · · vr be a path of maximal length r in G. Every vertex adjacent to vr must lie on this path. Let i be the smallest of 0, . . . , r for which vi is adjacent to vr. d(vr) ≥ 2, so i ≤ r − 2. Then vi · · · vrvi is a cycle containing all the vertices adjacent to vr so its length (the number of edges) is not less than d(vr) + 1, which in turn is not less than δ(G) + 1. 1.1.7 Complement Definition 1.8 The complement of a simple graph G is the graph G with the same vertex set V (G), such that two vertices are adjacent in G if and only if they are not adjacent in G. A graph which is isomorphic to its complement is self-complementary. 9 It is clear that the complement of G is G. Examples (i) A graph G and its complement G: (ii) C5 and C5 are the same graph. Thus C5 is self-complementary. Example Show that in any set of at least six people there are either three mutual acquaintances or three mutual strangers. Represent the n people by vertices of a simple graph G, with an edge joining two of them if and only if they are acquainted. In the complete graph Kn = G ∪G, each vertex v is adjacent to all the others. Thus v is adjacent to at least three vertices of a graph G′ which is either G or G. If two of these three vertices are adjacent in G′ then, together with v, they form a triangle in G′; otherwise they form a triangle in G′. Thus at least one of G and G contains a triangle, so in G there are either three vertices all adjacent to one another, or three vertices with no edges between any of them. The result follows. 1.1.8 Bipartite graphs Definition 1.9 A graph G is bipartite if V (G) is the union of disjoint sets U and W such that every edge of G joins an element of U to an element of W . Such a graph can be denoted by G(U,W ). The sets U and W form a bipartition of V (G). Let U and W have orders r, s respectively. If there is exactly one edge from each vertex in U to each vertex in W , and no other edges, then G(U,W ) is the complete bipartite graph Kr,s (or Ks,r – the order does not matter). A bipartite graph; the complete bipartite graph K3,2; the complete bipartite graph K1,5, also known as the star S6 (or S5 in some books). Note that isolated vertices can be included in U or W . A null graph with two or more vertices is bipartite. 10 Proposition 1.4 A graph with at least two vertices is bipartite if and only if it con- tains no cycle of odd length. Proof (⇒): Suppose G(U,W ) is bipartite.
If there is a cycle in G, it can be written in the form u1w1u2w2 · · ·urwru1. Then the number of edges in the cycle is 2r, which is even, so there can be no odd cycles. (⇐): Suppose G does not contain an odd cycle. Then no connected subgraph of G contains an odd cycle, so we may assume that G is connected. If G has only one edge, it joins two vertices (as G has no loops) so G is bipartite. Make the inductive hypothesis that all graphs with no odd cycles and fewer edges than G are bipartite. Let uv be any edge of G. By hypothesis, the graph G − uv has a bipartition into vertex sets X and Y . Suppose u, v ∈ X (the reasoning is identical if both are in Y ). If there is a path P from u to v in G − uv, it alternates between X and Y so has even length. Then P ∪ uv is a closed walk of odd length in G, so it contains an odd cycle by Exercises 1.1 Question 18. But G is assumed to contain no odd cycles. Thus one of u and v is in X and the other in Y , so X and Y form a bipartition of G. The result follows by induction. It may not be obvious whether a given graph is bipartite. It will be so if there is a way of assigning two colours (or other labels) to the vertices such that no two vertices have the same colour. If we can find an odd cycle, the graph is certainly not bipartite. Example The first two of the following graphs are bipartite, as the alternating black and white vertices show; in fact they are both K3,3 in disguise. The third graph is not bipartite as it contains a triangle, which is an odd cycle. 11 1.1.9 Degree sequences and the Havel-Hakimi condition Definition 1.10 The degree sequence of a graph is an ordered list of the degrees of the vertices. A list of integers is graphical if it is the degree sequence of a simple graph. In Example 1.1.1, the degree sequence is 6, 6, 5, 3. (Some books write the sequence in non-decreasing rather than non-increasing order.) By Proposition 1.1, a degree sequence must contain an even number of odd terms. It can be shown that any such sequence is the degree sequence of some graph or multigraph (not necessarily unique). To determine whether a degree sequence represents a simple graph, we can use: Proposition 1.5 (The Havel-Hakimi condition) A non-increasing list of integers s0, s1, . . . , sn, where s0 = d, is graphical if and only if the list s1 − 1, s2 − 1, . . . , sd − 1, sd+1, sd+2, . . . , sn is graphical. The proof of this result (omitted) establishes that some graph with non-increasing degree sequence s0, . . . , sn has a vertex of degree d = s0 adjacent to d vertices of degrees s1, . . . , sd. This need not be true for every graph with the given degree sequence, but at least one must exist. It can be constructed by successively applying the condition until a recognisable sequence is obtained. Examples (i) 4, 3, 2, 1, 1 is not graphical, because the number of odd numbers is not even. (ii) Consider the list 5, 5, 4, 3, 2, 1. Successively applying the Havel-Hakimi condition gives 4, 3, 2, 1, 0, then 2, 1, 0,−1. This is not graphical, as −1 cannot be the degree of a vertex, so 5, 5, 4, 3, 2, 1 is not the degree sequence of a simple graph. However, a multigraph with degree sequence 4, 3, 2, 1, 0 can be constructed. Then joining a new vertex of degree 5 to each of these five vertices produces a multigraph of order 6 with degree sequence 5, 5, 4, 3, 2, 1: 12 (iii) Consider the list 4, 3, 3, 3, 1. Successively applying the Havel-Hakimi condition gives 2, 2, 2, 0, then 1, 1, 0. This is graphical since it is the degree sequence of a single edge together with an isolated vertex. From this we can construct simple graphs with degree sequences 2, 2, 2, 0 and finally 4, 3, 3, 3, 1, as shown. 13 1.1.10 Exercises 1. Consider the following multigraph G (a) State the degree of each vertex. (b) Verify each part of Proposition 1.1 for G. (c) Draw the following graphs: (i) G− uw, (ii) G− x, (iii) G− {u,w}, (iv) G \ wz, (v) the subgraph H of G induced by {v, w, y, z}, (vi) the complement of the simple graph H − `, where ` is the loop at y. (d) Find a connected spanning subgraph of G with the smallest possible num- ber of edges. (e) Find each of the following: (i) a trail of length 7 from t to y, (ii) a path of length 6 from u to x, (iii) a cycle of length 6. (f) Show that G is not bipartite. 2. Which of the following are regular? For those that are, state the degree of regularity. (a) Nn, (b) Kn, (c) Pn, (d) Wn, (e) Kr,s. 3. Let G be an r-regular graph with n vertices and m edges. Find a relationship between m,n and r. Deduce that there are no 5-regular graphs with 7 vertices. 4. For each of the Platonic graphs on Page 5, state whether the graph is regular, and if so of what degree. 5. Find the largest possible number of vertices in a graph with 19 edges in which every vertex has degree at least 3. 6. G is a graph of order 9 in which each vertex has degree 5 or 6. Prove that G has either at least five vertices of degree 6 or at least six vertices of degree 5. 7. The pigeon-hole principle states that if n objects are put into fewer than n boxes then at least one box has more than one object in it. Use this to show that in a finite simple connected graph with more than one vertex, there are at least two vertices which have the same degree. 8. Show that the number of distinct labelled simple graphs with n vertices is 2n(n−1)/2. 14 9. Draw each of the following graphs and its complement: N3, K4, P3, W5, K3,2. Are any of these graphs self-complementary? 10. Show that a self-complementary simple graph of order n has n(n− 1) 4 edges. Deduce that the order of such a graph is congruent to 0 or 1 (modulo 4). 11. Show that Cn is bipartite if and only if n is even. 12. Draw the eleven non-isomorphic unlabelled simple graphs with four vertices. Give the degree sequence of each one. 13. Determine whether each of the following is the degree sequence of (i) a simple graph, (ii) a multigraph, and draw the graph if one exists. (a) 7, 5, 3, 1, (b) 3, 2, 2, 1, (c) 4, 3, 3, 2, 1, (d) 5, 5, 4, 3, 3, 2. 14. n people go on separate holidays. Each sends a postcard to exactly three of the others. For each of n = 4, 5, 6, 7, 8, is it possible that each person receives a card from precisely the three to whom they sent cards? 15. Let G be a 2-regular connected finite graph. By induction on the number of edges in G, prove that G is a cycle. 16. e is an edge which is common to two cycles in a graph G. Prove that G contains a cycle that does not include e. 17. Suppose r < s. Show that Kr+1,s−1 has no fewer edges than Kr,s. Hence show that the maximum number of edges in Kr,s, where r + s = n, is⌊ n2 4 ⌋ . 18. Prove that any closed walk of odd length contains a cycle of odd length. 15 1.2 Connectedness of graphs 1.2.1 Definition of connectedness Definition 1.11 Vertices u and v are connected in a graph G if there is a walk from u to v in G. A connected graph is a graph G in which every two vertices are connected. If this is not the case then G is disconnected. For any v ∈ V (G), the set of all vertices of G that are connected to v is the compo- nent of G containing v. Examples (i) Nn is disconnected. It has n components, each consisting of a single vertex. (ii) The following graph has four components: Proposition 1.6 Let G be a simple graph with n vertices, m edges and c components. Then n− c ≤ m ≤ (n− c)(n− c+ 1) 2 . Proof For the lower bound: clearly m ≥ n− c when m = 0, since c = n in that case. Starting from the null graph Nn, we can construct G by successively adding edges. Each new edge increases m by 1 and either keeps c the same or reduces it by 1 (by connecting two components), so the inequality m ≥ n− c is preserved at each stage. The upper bound holds when G is connected, since then c = 1 and G is a subgraph of Kn. If G is disconnected, let H1, . . . , Hc be the components of G and, for each i, let Hi have ni vertices. The maximum number of edges of Hi occurs when it is the complete graph Kni , so we may assume Hi has order ni(ni − 1) 2 . Suppose there are two components Hi, Hj with more than one vertex: say ni ≥ nj ≥ 2. Replacing Hi and Hj by complete graphs with ni + 1 and nj − 1 vertices respectively will keep n and c unchanged, while the number of edges is increased by (ni + 1)ni 2 + (nj − 1)(nj − 2) 2 − ni(ni − 1) 2 − nj(nj − 1) 2 = ni − nj + 1 > 0. 16 This procedure can be repeated until some component can be made no larger. Thus for any given n and c, the maximum value of m occurs when one component is the complete graph Kn−c+1 and the other c− 1 components are isolated vertices. In this case m = (n− c)(n− c+ 1) 2 . For a connected graph, c = 1. Then Proposition 1.6 gives n− 1 ≤ m ≤ n(n− 1) 2 , as we already knew. 1.2.2 Separating and disconnecting sets Definition 1.12 A separating set of a graph G is a set of vertices whose removal (together with their incident edges) increases the number of components of G. A cut vertex or cutpoint of G is a single vertex which forms a separating set. The (vertex) connectivity κ(G) is the order of the smallest separating set in G. If κ(G) ≥ k then G is k-connected. A disconnecting set of a graph G is a set of edges whose removal increases the number of components of G. A cutset is a disconnecting set which has no proper subset that is a disconnecting set. A bridge is a single edge which forms a cutset. The edge connectivity λ(G) is the order of the smallest disconnecting set in G. If λ(G) ≥ k then G is k-edge-connected. Thus a connected graph is k-connected/k-edge connected if the number of vertices/edges that must be removed to disconnect it is k or more. There is no separating set in Kn. We define κ(Kn) to be n−1, as removing this many vertices reduces it to an isolated vertex. κ(Nn) and λ(Nn) are defined to be 0. In a graph other than P2, at least one end-vertex of a bridge must be a cut vertex. Examples (i) In the graph G of Example 1.1.1, the smallest separating set is {v2, v3}, so κ(G) = 2. Thus G is 2-connected, and hence also 1-connected, but not 3-connected. {e4, e5, e6, e7, e8} is a disconnecting set, and indeed a cutset. {e2, e3, e4, e5} is a dis- connecting set but not a cutset. The smallest cutsets are {e2, e3, e4} and {e8, e9, e10}, so λ(G) = 3. Thus G is 3-edge-connected, and also 1- and 2-edge connected, but not 4-edge-connected. (ii) In the following graph G, κ(G) = λ(G) = 1. e, x and y are cut vertices. Each of ex and yw is a bridge. If either is removed, the resulting graph has two components. If both are removed then we get a graph with three components, one being an isolated vertex. 17 Proposition 1.7 Let G be a connected graph with minimum vertex degree δ(G). Then κ(G) ≤ λ(G) ≤ δ(G). Proof If G = Kn for some n, then κ(G) = λ(G) = δ(G) = n− 1. Now suppose G 6= Kn. The set of all edges incident with any vertex is a disconnecting set (as their removal isolates that vertex), so in any graph, λ(G) ≤ δ(G). Assume G is a simple graph. If G = N1 then κ(G) = λ(G) = 0. Otherwise λ(G) ≥ 1. Let {e1, . . . , eλ(G)} be a cutset, so G has subgraphs H1, H2 which become disonnected components when the cutset is removed. Let x be the number of vertices of H1 that are incident to an edge in the cutset. Clearly x ≤ λ(G). If x < λ(G), then deleting these x vertices, with their incident edges, disconnects G so κ(G) ≤ x. Hence κ(G) ≤ λ(G). If x = λ(G), then consider any vertex in H1, v, say. Since G is simple, H1 is simple so in H1, d(v) ≤ x− 1. Since x = λ(G), in G, exactly one of the edges in the cutset is incident to v. Hence in G, d(v) = x. Therefore, we can construct a separating set of size x by deleting all the adjacent vertices to v, so again κ(G) ≤ λ(G). If G is not a simple graph, removing loops and multiple edges will produce a simple graph G′ such that κ(G) = κ(G′) ≤ λ(G′) ≤ λ(G), so the result holds for G. Proposition 1.8 Let G be a connected graph with at least three vertices. Then G has a cut vertex if and only if there is a pair of vertices in G that do not lie on the same cycle. Proof Suppose v is a cut vertex of G. Then G− v has two components; let u be in one and w in the other. If u and w lie on a cycle in G then v must also lie on the cycle. With the path u · · · v · · ·w removed, the rest of the cycle is another path from u to w which connectes the two components in G− v. This is impossible, so u and w do not lie on a cycle in G. Conversely, assume G has no cut vertex. We need to show that every two vertices lie on some cycle. Let u and w be distinct vertices of G. 18 If `(u,w) = 1, there is an edge e = uw which is not a bridge, since neither u nor w is a cut vertex. Thus there is another path from u to w, which together with e forms a cycle that includes u and w. Make the inductive hypothesis that any two vertices u,w where `(u,w) < r lie on some cycle. Now suppose `(u,w) = r. Let P = v0v1 · · · vr be a path from u = v0 to w = vr. As `(v0, vr−1) < r, there is a cycle C in G containing v0 and vr−1 by the hypothesis. C can be split into two paths P1 and P2 from v0 to vr−1 which have no other vertices in common. G − vr−1 is connected, as G has no cut vertex, so there is a path P3 from u to w in G− vr−1. Let x be the last vertex of P3 that lies in C; assume x ∈ P1. Let P ′1 be the part of P1 from u to x and Q ′ 1 the part from x to vr−1. Let P ′3 be the part of P3 from u to x and Q ′ 3 the part from x to w. Then P ′1 ∪Q′3 ∪wvr−1 ∪ P2 is a cycle in G containing u and w. The result follows by induction. This result can also be stated as follows: G has no cut vertex if and only if every two distinct vertices are connected by two paths that are internally-disjoint, i.e. they have no common vertices except their initial and final vertices. In the above proof, P ′1 ∪Q′3 and P2 ∪ vr−1w are such paths. 19 1.2.3 Exercises 1. G is a simple graph with four components and ten vertices. Find the possible numbers of edges of G. 2. Use Proposition 1.6 to show that a simple graph with 7 vertices and 16 edges must be connected. 3. For each of the following graphs, identify all cut vertices and bridges (if any). State the connectivity and the edge connectivity. In (b), find cutsets of order λ(G) + 1 and λ(G) + 2. 4. State the connectivity and the edge connectivity of the following graphs. 5. Draw a connected graph G (not necessarily simple) in each of the cases: (a) κ(G) = 1, λ(G) = δ(G) = 2, (b) κ(G) = 2, λ(G) = δ(G) = 3. 6. G is a finite graph (not necessarily connected) which has exactly two vertices u and v of odd degree. Show that there is a path from u to v in G. 7. G is a graph in which every vertex has even degree. Show that there are no bridges in G. Deduce that if G is connected, it is 2-edge-connected. 8. c is a cut vertex of a connected graph G. Prove that there are vertices u and v, distinct from c, such that c lies on every path from u to v. 9. e is a bridge in a connected graph G. Prove that e does not lie in a cycle in G. 10. (a) Prove that the complement of a disconnected simple graph is connected. (b) Show that the complement of a connected simple graph may or may not be connected. 11. Show that if v is a vertex of a simple connected graph G then G− v = G− v. Using this and the result of Question 10 (a), show that no vertex can be a cut vertex of both G and G. 20 12. G is a simple graph of order n, such that δ(G) ≥ ⌊n 2 ⌋ . (a) Show that G is connected. (b) Suppose λ(G) < δ(G). Show that if λ(G) edges of G are deleted, each component of the resulting graph has at least δ(G) + 1 vertices. Deduce that λ(G) = δ(G) in this case. 21 1.3 Eulerian and Hamiltonian graphs 1.3.1 Eulerian graphs The origin of Graph Theory is usually regarded as being Euler’s solution of the Ko¨nigsberg Bridges problem in 1736. The Prussian city of Ko¨nigsberg (now Kalin- ingrad in Russia) has four land areas linked by seven bridges. The problem was whether it was possible to start in one of the four regions and cross each bridge exactly once before returning to the starting point. Euler’s model represents the land areas by the vertices of a graph and the bridges by edges. The question is then whether this graph contains a trail that is closed (i.e. the initial and final vertex are the same) and includes each edge. Definition 1.13 An Eulerian trail in a graph is a closed trail which includes every edge. An Eulerian graph is a graph which has an Eulerian trail. Thus an Eulerian graph is one which can be drawn in a plane, starting and finishing at the same point, without retracing any edge and without lifting the pen. Note that while in general a trail need not be closed, an Eulerian trail is. For that reason, some books call it an Eulerian tour, and use ‘Eulerian trail’ to mean any trail (open or closed) that includes all the edges. Proposition 1.9 For a non-trivial connected graph G, the following are equivalent: (i) G is Eulerian, (ii) every vertex of G has even degree, (iii) G is a union of edge-disjoint cycles. Proof (i) ⇒ (ii) If G is Eulerian then clearly it must be connected. An Eulerian trail passes in and out of each vertex v, contributing 2 to d(v) each time it does so. As every edge incident to v is in the trail, d(v) is even. 22 (ii) ⇒ (iii) The result is clearly true for the smallest connected graph satisfying (ii), namely a loop, which is a single cycle. Make the inductive hypothesis that it is true for all graphs that satisfy (ii) and have fewer edges than G. As G is connected, no vertex has degree 0 so every vertex has degree ≥ 2. Thus by Proposition 1.3 G contains a cycle C, say. If G = C we have the result. Otherwise remove all the edges of C from G. The resulting graph H (which may be disconnected) has fewer edges than G. Every vertex of H has even degree, since the vertex degrees are either unchanged or reduced by 2. By the hypothesis each non-trivial component of H is a union of edge-disjoint cycles, hence so is G. The result follows by induction. (iii) ⇒ (i) Let C and H be as above. By traversing C, following each cycle in H when it is first encountered, an Eulerian trail in G is obtained. The solution of the Ko¨nigsberg Bridges problem is now immediate. The graph has vertices of odd degree (indeed they are all odd) so no Eulerian trail exists. The pro- posed tour of the city is impossible. Given an Eulerian graph G, an Eulerian trail can be found as follows (Hierholzer’s algorithm): start at any vertex. By Proposition 1.9 (iii), v lies on a cycle. If there is a vertex w in this cycle that is incident to an edge not yet included, form another cycle from w to w with only edges that have not already been used. Repeat until all edges are included. We then have a set of edge-disjoint cycles whose union is an Eulerian trail. Example This graph has degree sequence 4, 4, 4, 4, 2, so it is Eulerian Starting at u, we can form the obvious cycle uvyzxu. We can also find cycles vwzv and xwyx. The union of these edge-disjoint cycles is an Eulerian trail uvwzvyzxwyxu. Definition 1.14 A semi-Eulerian trail in a graph is an open trail which includes every edge. A semi-Eulerian graph is a non-Eulerian graph which has a semi-Eulerian trail. Proposition 1.10 A connected graph is semi-Eulerian if and only if it has exactly two vertices of odd degree. 23 Proof Suppose there are just two vertices u, v of odd degree. Adding an edge uv produces a graph in which all vertices have even degree, so it is Eulerian. An Eulerian trail from u to u becomes a semi-Eulerian trail from u to v when we remove uv. Conversely, suppose there is a semi-Eulerian trail v1 · · · vn but no Eulerian trail. The edges in this trail have the form v1v2, v2v3, . . . , vn−2vn−1, vn−1vn. The vertices v1, . . . , vn need not all be distinct but each appears an even number of times in the list of edges, except for v1 and vn. As every edge is in the trail, all but two of the vertices have even degree. This shows that there is no trail that crosses each of the Ko¨nigsberg bridges once, even if the starting and finishing point need not be the same, since there are more than two odd-degree vertices. In the route inspection problem, also known as the Chinese postman problem, a net- work of roads is represented by a graph in which each edge is assigned a weight, i.e. a number representing the distance along that edge, or the cost of travelling along it, or some other relevant value. The problem is to find a closed walk, of minimum total weight, including each edge at least once. In an Eulerian graph, the solution is an Eulerian trail. In a semi-Eulerian graph, the solution is a semi-Eulerian trail together with a minimum-weight path between the two odd-degree vertices. Example The weighted network shown has two odd-degree vertices, A and E, so it is semi-Eulerian. A semi- Eulerian trail between A and E has total weight 32. The minimum-weight path between A and E is ABGE, of weight 4. Thus the smallest possible total weight of a closed walk that includes each edge is 36. 1.3.2 Hamiltonian graphs Several well-known mathematical problems require a graph to be traversed in such a way that each vertex is visited only once, starting and finishing at the same point - for example the travelling salesman problem, in which a number of cities need to be visited at minimal cost. The solution involves finding a cycle of the following type, named after Sir William Hamilton. 24 Definition 1.15 A Hamiltonian cycle in a graph G is a closed path which passes through each vertex of G exactly once. A Hamiltonian graph is a graph which has a Hamiltonian cycle. A non-Hamiltonian graph G is semi-Hamiltonian if there is a non-closed path in G which includes every vertex. The Knight’s Tour problem on a chessboard requires a knight to start on one square and make legitimate moves that visit every square once, returning to the starting point. This can be modelled by a graph with vertices representing the squares and an edge joining any two squares that are connected by a knight’s move. The problem is to find a Hamiltonian cycle. This can be generalised to m× n boards. In a graph with only one vertex, the only possible Hamiltonian cycle is a single loop. With just two vertices, a Hamiltonian cycle can only be a pair of parallel edges. If there are three or more vertices then loops and parallel edges cannot form part of a Hamiltonian cycle, so they can be ignored when looking for such a cycle. Furthermore, a Hamiltonian graph cannot contain a cut vertex so it must be 2-connected. Proposition 1.11 Let G be a simple graph with n vertices, where n ≥ 3. Each of the following is a sufficient condition for G to be Hamiltonian: (i) d(u) + d(v) ≥ n for every pair of non-adjacent vertices u and v (Ore’s theorem), (ii) d(v) ≥ n 2 for each vertex v (Dirac’s theorem). Proof Suppose condition (i) holds and G is not Hamiltonian. Add extra edges to G, which will certainly preserve the inequality, until a graph G′ is obtained which would be made Hamiltonian by adding another edge. (This is possible since Kn is clearly Hamiltonian.) Now in G′ there must be a path of the form v1 · · · vn, passing through all the vertices, which would become a Hamiltonian cycle with the edge vnv1 added. v1 and vn are not adjacent in G so d(v1) + d(vn) ≥ n by assumption, hence each of v2, . . . , vn−1 must be adjacent to at least one of v1 and vn, and at least two must be adjacent to both. Suppose that whenever vi is adjacent to v1, vi−1 is not adjacent to vn. Let k be the largest number for which vk is adjacent to v1. Then vk, vk−1, . . . , v2 are adjacent to v1 but not to vn, and vk+1, . . . , vn−1 are adjacent to vn but not to v1. But then d(v1) + d(vn) = n − 2 < n. Thus there is some vertex vi, adjacent to v1, such that vi−1 is adjacent to vn in G (and in G′). 25 Then v1v2 · · · vi−1vnvn−1 · · · viv1 is a Hamiltonian cycle in G′, giving a contradiction. Hence if (i) holds, G is Hamiltonian. Clearly (ii) implies (i). Note that the conditions in Proposition 1.11 are sufficient but not necessary. There are plenty of Hamiltonian graphs that do not satisfy the conditions in Dirac’s or Ore’s theorem, such as the cycle graphs Cn for n ≥ 5. Examples G1 has 8 vertices, each with degree 4, so G1 is Hamiltonian. G2 has 7 vertices, and each of the non-adjacent pairs has degree sum 7 or more, so G2 is also Hamiltonian. There is no si mple necessary and sufficient condition for a graph to be Hamiltonian. The following necessary condition is sometimes useful. Proposition 1.12 If G is a Hamiltonian graph then for every non-empty proper subset S of V (G), the number of components of G− S is less than or equal to |S| Proof Let C be a Hamiltonian cycle in G and let S be a non-empty proper subset of V (G). Removing all the vertices in S from C separates C into at most |S| components, this maximum occurring when no two vertices in S are adjacent in C. C is a spanning subgraph of G, so C − S is a spanning subgraph of G − S. Thus G− S cannot have more components than C − S. The result follows. Example Five people A,B,C,D,E are to be seated around a circular table. The following pairs are acquainted: (A,C), (A,E), (B,C), (B,E), (C,D), (D,E). Is it possible to arrange them so that everyone is sitting between two acquaintances? Represent the people as vertices of a graph, with edges joining acquaintances. We see that deleting the two vertices C and E, and their incident edges, would separate the graph into three components (each an isolated vertex). As 3 > 2, Proposition 1.12 shows that no Hamiltonian cycle exists so the desired arrangement is not possible. 26 1.3.3 Exercises 1. Find conditions for the following to be Eulerian or semi-Eulerian: Cn, Wn, Kn, Kr,s. 2. Show that the graph of the octahedron is Eulerian and find an Eulerian trail in it. Which of the other Platonic graphs are Eulerian? 3. Prove that in any connected graph there is a closed walk which traverses each edge exactly twice. 4. Show that the following graph G is semi-Eulerian. State how G can be made Eulerian by adding an edge. Find a semi-Eulerian trail in G. 5. The network represents eight towns and the roads joining them, with distances given for each road link. A courier needs to drive along each road at least once and return to the starting point. Show that the graph can be made Eulerian by adding imaginary extra roads between two pairs of towns, and that there are three ways of doing this. Hence find the minimum distance that the courier must cover. 6. A king in chess can move to a horizontally or vertically adjacent square. Show that on a normal 8 × 8 board it is impossible for a king to make a sequence of such moves which cross every line between squares exactly once. Find the dimensions of all square or rectangular boards for which this is possible. 7. For n ≥ 3, determine which of the following are Hamiltonian: Cn, Wn, Kn. 8. Show that a bipartite graph with an odd number of vertices is not Hamiltonian. 9. Prove that if a bipartite graph G(U,W ) is Hamiltonian then U and W contain the same number of vertices. 10. Classify each of the following as Eulerian, semi-Eulerian, Hamiltonian, semi- Hamiltonian or none of these: 27 11. Consider an n× n board, with squares coloured alternately black and white as usual. Given that a knight’s move always moves from a square of one colour to a square of the other colour, show that a knight’s tour is impossible when n is odd. 12. Six people A,B,C,D,E, F are to be seated around a circular table. Determine whether it is possible to arrange them so that everyone is sitting between two acquaintances, in the cases where the following pairs are acquainted: (a) (A,B), (A,C), (B,D), (B,F ), (C,D), (C,E), (D,F ), (E,F ). (b) (A,C), (A,D), (A,F ), (B,C), (B,D), (B,E), (C,E), (C,F ), (D,E), (D,F ). (c) (A,C), (A,F ), (B,C), (B,E), (C,D), (C,E), (C,F ), (D,E). 13. Let G be a connected simple graph with n ≥ 3 vertices. Suppose that there is a positive integer k ≤ n such that d(u) + d(v) ≥ k for every pair of non-adjacent vertices u and v. Show that there is a path of length k in G. 14. G is a simple graph with n vertices. (a) Let G′ = G − {u, v}, where u and v are any two non-adjacent vertices in G. Show that |E(G′)| = |E(G)| − d(u)− d(v). (b) Now suppose G has ( n− 1 2 ) + 2 edges. Use the fact that G′ is a subgraph of Kn−2 to show that ( n− 1 2 ) + 2− d(u)− d(v) ≤ ( n− 2 2 ) . (c) Hence show that d(u) + d(v) ≥ n and deduce that G is Hamiltonian. (d) Give an example of a non-Hamiltonian graph with ( n− 1 2 ) + 1 edges. 28 1.4 Trees 1.4.1 Trees Definition 1.16 A tree is a connected graph which is cycle-free, i.e. it contains no closed paths. A forest is a graph in which each component is a tree. Here are some trees. Their union is a forest. From the diagrams, it appears that any non-trivial tree with n vertices has n − 1 edges. Assuming this (which is proved below), in a tree with n > 1 vertices and m edges we have n∑ i=1 d(vi) = 2m = 2n − 2 < 2n, so there are at least two vertices of degree 1. Proposition 1.13 For a graph G with n ≥ 2 vertices and m edges, the following are equivalent: (i) G is a tree; (ii) there is a unique path between any two vertices in G; (iii) G is connected and every edge of G is a bridge; (iv) G is connected and m = n− 1; (v) G contains no cycles and m = n− 1; (vi) G contains no cycles and, if any two vertices of G are joined by a new edge e, then G ∪ {e} has exactly one cycle. Proof (i) ⇒ (ii): As G is connected, there is a path between any two vertices. If there were two such paths, their union would contain a cycle, so the path is unique. (ii)⇒ (iii): If (ii) holds then G must be connected. Any edge uv of G is the unique path joining u and v so if it is removed then there is no path from u to v, making G disconnected. Thus uv is a bridge. 29 (iii) ⇒ (iv): If n = 2 then there is one edge, so m = n − 1. Now let n > 2 and ssume that the implication holds when the number of vertices is less than n. When there are n vertices, deleting an edge produces two connected components G1, G2, each satisfying (iii), with n1, n2 vertices where n1 < n, n2 < n. By the hypothesis, G1 and G2 have n1 − 1, n2 − 1 edges respectively, so G has n1 − 1 + n2 − 1 + 1 = n− 1 edges. The result follows by induction. (iv) ⇒ (v): Suppose G is connected with m = n − 1 and has a cycle of length r. This contains r vertices and r edges. Each of the n − r vertices not on this cycle is incident with one edge on a shortest path from it to the cycle, so G has at least n edges, i.e m ≥ n. This contradicts (iv), so G is cycle-free. (v) ⇒ (vi): Suppose G is cycle-free with m = n − 1. If G has k components then adding k − 1 edges would create a tree with n vertices, so m + (k − 1) = n − 1 and thus k = 1, i.e. G is connected. Hence G is a tree so by (ii) there is a unique path P between any two vertices u, v of G. Joining u and v by a new edge e gives a unique cycle P ∪ {e} in G ∪ {e}. (vi) ⇒ (i): If G is not connected then any two vertices in different components can be joined without creating a cycle. Thus if (vi) holds then G is connected and cycle-free, so G is a tree. We can distinguish between labelled and unlabelled trees. Here we use numbers to label the vertices. The following are isomorphic, but distinct, labelled trees. We see that there are three different labelled trees with 3 vertices. 1.4.2 Prufer sequences Proposition 1.14 The number of distinct labelled trees with n vertices is nn−2. Proof The result is clear if n = 1 or n = 2. Now assume n ≥ 3. Given a tree with its vertices labelled 1, . . . , n, we construct a sequence of n − 2 elements of {1, . . . , n} as follows: Select the end-vertex with the smallest label; call this label b1. Let a1 be the vertex adjacent to b1. Delete b1 and the edge a1b1, leaving a labelled tree with n−1 vertices. 30 Repeat the procedure: select the end-vertex of the new tree with the smallest label b2 and let the adjacent vertex be a2. Delete b2 and the incident edge. Continue until only two vertices remain, at which point we have a sequence a1, a2, . . . , an−2. Conversely, given such a sequence a1, . . . , an−2, let b1 be the smallest label in {1, . . . , n} that is not in the sequence. Join the points labelled b1 and a1. Let b2 be the smallest label not in b1, a2, . . . , an−2 and join it to a2. Repeat until there are only two labels not in b1, . . . , bn−2, and join the points with these labels to get a tree. This tre e will, by the process described earlier, generate the sequence that we started with. Thus there is a one-to-one correspondence between labelled trees and sequences. There are n possible values for each of n−2 terms, so the number of possible sequences is nn−2. Definition 1.17 The sequence obtained in the above proof is called a Pru¨fer se- quence. Each such sequence of n−2 positive integers uniquely determines a labelled tree with n vertices, and vice-versa. The Pru¨fer sequence for a tree has 2 fewer terms than the number of vertices in the tree. To construct the Pru¨fer sequence from the tree: Remove the end-vertex with the smallest label, and its incident edge, from the tree. Put the label of the adjacent vertex (now an end-vertex) in the sequence. Repeat with the remaining tree until only two vertices remain - do not put them into the sequence. Note that all the numbers in the sequence are labels of vertices that were not end- vertices in the original tree. Example The smallest end-vertex label is 2. It is adjacent to 6. Delete 2 and start the sequence with 6. The smallest end-vertex label is now 3. It is adjacent to 1. Delete 3. The sequence becomes 6, 1. The smallest end-vertex label is now 4. It is adjacent to 1. Delete 4. The sequence becomes 6, 1, 1. 31 The smallest end-vertex label is now 1. It is adjacent to 6. Delete 1. The sequence becomes 6, 1, 1, 6. Only two vertices (5, 6) remain so the Pru¨fer sequence is complete: it is 6, 1, 1, 6. To construct the tree from the Pru¨fer sequence: Start with a null graph Nn, where n is 2 more than the length of the sequence. Take the smallest number in the list 1, . . . , n that is not in the sequence. Join this to the first term in the sequence. Delete the numbers from the two lists and repeat with the remaining lists until only two numbers remain in the first list. Join these and the tree is complete. Example Construct a tree with the Pru¨fer sequence 2, 3, 2, 1, 5. The tree will have seven vertices. 4, 6 and 7, which are not in the sequence, will be end-vertices. Comparing 1, 2, 3, 4, 5, 6, 7 with 2, 3, 2, 1, 5, the smallest number not in the Pru¨fer sequence is 4. Join it to the first in the sequence, 2. Comparing 1, 2, 3, 5, 6, 7 with 3, 2, 1, 5, the smallest number not in the Pru¨fer sequence is 6. Join it to the first in the reduced sequence, 3. Comparing 1, 2, 3, 5, 7 with 2, 1, 5, the smallest number not in the Pru¨fer sequence is 3. Join it to 2. Comparing 1, 2, 5, 7 with 1, 5, the smallest number not in the Pru¨fer sequence is 2. Join it to 1. Comparing 1, 5, 7 with 5, the smallest number not in the Pru¨fer sequence is 1. Join it to 5. Now only 5 and 7 remain. Join them to complete the tree: 32 1.4.3 Spanning trees and forests Definition 1.18 A spanning tree for a graph G is a subgraph T , which is a tree, such that V (T ) = V (G). If G is disconnected, a spanning forest for G is a union of spanning trees for all its components. Example The Petersen graph, with 10 vertices, and two spanning trees, each with 10 − 1 = 9 edges. Proposition 1.15 A graph is connected if and only if it has a spanning tree. Proof Assume G has a spanning tree T . Then there is a path in T , and hence in G, between any pair of vertices, so G is connected. Conversely, suppose G is connected. If G is not a tree then it contains a cycle. Re- moving one edge of the cycle will not disconnect G. If the remaining graph is not a tree, repeat the process. Continue until a tree is obtained. No vertices of G have been removed, so we have a spanning tree. It follows from Proposition 1.14 that there are nn−2 different spanning trees of Kn. From Proposition 1.15, every graph has a spanning forest. In a graph G with n vertices and c components, a spanning forest has n− c edges. Thus if G has m edges then m− n+ c edges must be removed from G to obtain a spanning forest. Proposition 1.16 Let T be a spanning forest of a graph G. Then (i) each cutset of G has an edge in common with T , (ii) each cycle of G has an edge in common with the complement of T . 33 Proof (i) Let S be a cutset of G, so if the edges in S are removed then some component H of G is split into disjoint subgraphs H1 and H2. As T is a spanning forest, it includes a spanning tree for H and thus contains an edge joining a vertex of H1 to a vertex of H2. This edge must be in S. (ii) Let C be a cycle in G and suppose no edge of C is in T . Then C is a subgraph of T , but T contains no cycles. We have a contradiction, so C has an edge in common with T . Definition 1.19 Let G be a graph with n vertices, m edges and c components. The cutset rank of G is ξ(G) = n− c. The cycle rank or nullity of G is γ(G) = m− n+ c. In particular, for a connected graph, γ(G) = m− n+ 1 and ξ(G) = n− 1. In some applications, a particular vertex of a tree is identified as a root and the graph is called a rooted tree. The root is usually shown at the bottom of a drawing. Any vertex can be a root; for example, the graph on the left can be drawn as the rooted tree on the right. Tree diagrams for probability problems are examples of rooted trees. In that case the root is usually shown on the left. 34 1.4.4 Exercises 1. Draw all the labelled trees with four vertices. By considering the possible lengths of longest paths, or otherwise, find all unlabelled trees with seven vertices. 2. Find the sum of the degrees of all the vertices in a tree with n vertices, where n ≥ 2. 3. Suppose a tree has an even number of edges. Show that it has at least one vertex of even degree. 4. Show that any tree T has at least ∆(T ) end vertices. 5. Show that every tree with more than one vertex is a bipartite graph. 6. Show that the complete graph Kr,s (where r, s ∈ N) is a tree if and only if at least one of r and s is 1. 7. Show that a semi-Hamiltonian tree must be a path graph. 8. Find the Pru¨fer sequence for each of the following labelled trees. 9. Draw labelled trees with Pru¨fer sequences (a) 1, 2, 3, 4, 5, 6, (b) 3, 2, 3, 4, 2, (c) 1, 2, 1, 2, 1, 2, (d) 7, 7, 7, 7, 7. 10. What can be said about trees with Pru¨fer sequences in which the terms are (a) all the same, (b) all different? 11. Let pk be the number of occurrences of the number k in a Pru¨fer sequence for a labelled tree T . Find the degree of vertex k in T . 12. T is a tree with n vertices in which every vertex has degree 1 or 3. Show that n is even and find the number of vertices of each degree, in terms of n. 13. Find the number of spanning trees of (a) a labelled complete graph K5, (b) the graph in Example 1.1.1. 35 14. Find the cycle rank and the cutset rank of each of the following: K5, K3,3, K3,3, W5, N5, the Petersen graph, a tree with n vertices. 15. For any n ≥ 2, let G be the graph obtained from Kn by deleting any one edge. Show that G has (n− 2)nn−3 spanning trees. 36 Chapter 2 Planar graphs, colouring, matching and flows 2.1 Planar graphs and dual graphs 2.1.1 Planar graphs Definition 2.1 A planar graph is a graph that can be drawn in a plane in such a way that edges intersect only at vertices to which they are incident. A plane graph is a planar graph drawn in such a way in a plane. It may not be apparent whether a given graph is planar. The following method can be applied to a Hamiltonian graph G. First find a Hamiltonian circuit C (which is not necessarily unique), then try to divide the edges that are not in C into two sets A and B, such that the edges in A and in B can be drawn, without crossing, inside and outside C respectively. If this is possible, G is planar. Example In the graph below, there is a Hamiltonian cycle tuxwvyzt. Draw this as a heptagon. If the edge zu is drawn inside the heptagon then zv and zw can also go inside without crossing. Then tx, tw and wy will have to go outside the heptagon. They can be drawn without crossing, as shown, so the graph is planar. We can check that the vertices have the same degrees as in the original drawing. The number of edges drawn must be half the sum of the degrees. 37 Definition 2.2 A face of a plane graph is a region bounded by edges. There is an infinite face lying outside the graph. The degree (or face degree) of a face F , denoted by d(F ), is the number of edges that form the boundary of F . If an edge is incident to a vertex of degree 1 inside F , it contributes 2 to d(F ). If all faces have the same degree r then the graph is face-regular of degree r. Example This plane graph has 9 vertices, 12 edges and 5 faces, labelled F1, . . . , F5. The face degrees are: d(F1) = 2, d(F2) = 8, d(F3) = 1, d(F4) = 3, d(F5) = 10. (The edges with end-vertices in- side F2 and F5 have each been counted twice.) Note that the sum of the face degrees, 24, is twice the number of edges. The following result, which corresponds to Proposition 1.1, shows why this is so. Proposition 2.1 (i) Let G be a plane graph with m edges and f faces F1, . . . , Ff . Then f∑ i=1 d(Fi) = 2m. (ii) The number of faces of odd degree in any plane graph is even. Proof (i) Each edge e has faces Fi and Fj (which may be the same) on either side of it. In calculating the sum of the face degrees, e is counted in both d(Fi) and d(Fj). Thus the sum of the face degrees is twice the number of edges. (ii) Suppose there are p odd-degree faces and q even-degree faces. Then the sum of the face degrees is the sum of p odd numbers and q even numbers. By (i) this sum is even, so p must be even. Proposition 2.2 (Euler’s formula) Let G be a connected plane graph with n ver- tices, m edges and f faces. Then n−m+ f = 2. 38 Proof If m = 1 then G has one edge, two vertices and one (infinite) face, so the result holds. Assume it holds for all connected plane graphs with fewer than m edges. Now let G have m edges. If G is a tree then m = n− 1 and f = 1, so n−m+ f = 2. If G is not a tree then it contains a cycle. Let e be an edge in this cycle. Removing e combines two faces into one, so G−e is a plane graph with n vertices, m−1 edges and f−1 faces. By the hypothesis, n−(m−1)+(f−1) = 2 and thus again n−m+f = 2. The result follows by induction on m. Now consider a convex polyhedron with n vertices, m edges and f faces. By projecting the figure onto a plane we obtain a plane graph with the same values of n,m and f ; one face of the polyhedron becomes the infinite face of the graph. Thus the formula n−m+ f = 2 holds for the polyhedron. We can use this to establish that the five platonic solids are the only convex polyhedra which are regular, in the sense that their faces all have the same number of edges, and the same number of edges meet at each vertex. That is, each vertex has the same degree d ≥ 3 and each face has the same degree r ≥ 3. By Propositions 1.1 and 2.1, dn = rf = 2m. Also n−m+ f = 2. Combining these equations gives 2m d − m + 2m r = 2, so 1 d + 1 r = 1 m + 1 2 where d, r,m ∈ N. This is impossible if d ≥ 4 and r ≥ 4, since then 1 d + 1 r ≤ 1 2 , so at least one of d and r is 3. Then the other one cannot be more than 5. The possible pairs (d, r) are thus (3, 3), (3, 4), (3, 5), (4, 3), (5, 3). When d = r = 3 we have 3n = 3f = 2m, so n = f = 4,m = 6, giving the tetrahedron. Similarly, the other pairs give the other Platonic solids. Proposition 2.3 Let G be a connected simple planar graph with n ≥ 3 vertices and m edges. Then m ≤ 3n− 6. If G contains no triangles then m ≤ 2n− 4. Proof Consider a plane drawing of G. As G is simple and has at least 3 vertices, each face is bounded by at least three edges. Thus if f is the number of faces then 2m ≥ 3f by Proposition 2.1. Now n−m+f = 2, so 2m ≥ 3(2+m−n). Hence 2m ≥ 6+3m−3n, so m ≤ 3n− 6. If G has no triangles then each edge is bounded by at least four faces, so 2m ≥ 4f , giving m ≤ 2n− 4. 39 2.1.2 Kuratowski’s theorem Proposition 2.4 K5 and K3,3 are non-planar graphs. Proof K5 and K3,3 are certainly connected simple graphs with more than two vertices. K5 has n = 5 vertices and m = 10 edges, so m > 3n − 6, hence by Proposition 2.3 K5 is non-planar. K3,3 is bipartite, so it contains no triangles. It has n = 6 vertices and m = 9 edges, so m > 2n− 4, hence by Proposition 2.3 K3,3 is non-planar. Proposition 2.5 Every simple planar graph G has at least one vertex whose degree is not more than 5. Proof Clearly the result holds for G if and only if it holds for each component of G, so we may assume that G is connected. If G has one or two vertices (indeed, up to six) then the result is obvious, so we may assume Proposition 2.3. Suppose each vertex has degree 6 or more. Then by Proposition 1.1, 2m = ∑ v∈G d(v) ≥ 6n, so m ≥ 3n. But by Proposition 2.3 m ≤ 3n− 6, giving a contradiction. Hence G has a vertex of degree ≤ 5. Definition 2.3 Graphs G1 and G2 are homeomorphic if they can both be obtained from a graph G by inserting new vertices of degree 2 on its edges. Each of G1 and G2 is then a subdivision of G. Proposition 2.6 (Kuratowski’s Theorem) A graph is planar if and only if it has no subgraph homeomorphic to K5 or to K3,3. Note that if G1 is obtained from G by inserting vertices of degree 2 then G1 is homeomorphic to G. Thus if we are given a graph G and can obtain K5 or K3,3 by deleting some edges and replacing paths by single edges, then G is non-planar. In particular, if G contains K5 or K3,3 then it is not planar. Example Consider the Petersen graph. It has no subgraph homeomorphic to K5 but it does have a subgraph homeomorphic to K3,3 as shown, so it is not planar. 40 See the exercises for another way of showing that this graph is non-planar. 2.1.3 Geometric dual Now let G be a plane graph with n vertices, m edges and f faces (including the infinite face). Construct a new graph G∗ as follows. Place a vertex in each face of G, including one in the infinite face. For each edge e in G, draw an edge which crosses e (and no other edge of G), joining the vertices in the faces on either side of e. Definition 2.4 The graph G∗ described above is called the geometric dual of G. Example The graph G on the left (with the thick edges) has four faces, including the infinite face. One face is the interior of a loop; another lies between a pair of parallel edges. The dual G∗ has vertices u1, u2, u3, u4, one in each face, as shown. The thinner lines show a way of constructing the dual as a plane graph – one edge of G∗ must cross each edge of G, and the edges must not cross except at vertices. The dual can be tidied up slightly, as on the right. Proposition 2.7 Let G be a plane connected graph with n vertices, m edges and f faces. Then G∗ is a plane graph with f vertices, m edges and n faces. 41 Proof G∗ is clearly a plane graph, by construction. It has f vertices, one in each of the f faces of G. One edge of G∗ is drawn to cross each edge of G, so G and G∗ have the same number of edges. It follows from Euler’s formula that G∗ has n faces. By the method of construction of G∗, a vertex of degree k in G corresponds to a face of degree k in G∗, and vice-versa. Given a planar graph G we can start with a plane drawing of G, which is not unique in general, and follow the given procedure to obtain a particular plane graph G∗. Starting from that plane drawing of G∗ (not re-drawing it to get an isomorphic graph) we can follow the procedure again to obtain (G∗)∗, which we write as G∗∗, the double dual of G. The construction of G∗∗ from G∗ reverses the steps in the construction of G∗ from G, so G∗∗ = G. In Example 2.1.3, if we start with G∗, place a vertex in each face and join them appropriately we get back to G. However, this will not necessarily work if we start with a different drawing of G∗, e.g. with the loop at u1 not enclosing u4. Thus isomorphic graphs do not in general have isomorphic duals. In the example below, the graphs with the thicker edges are different plane drawings of the same graphs. Their duals, drawn with the thinner edges, cannot be isomorphic because their vertices have different degrees: 6, 3, 3 in the first case and 5, 4, 3 in the second. Proposition 2.8 Let G be a plane graph with geometric dual G∗. A set of edges of G forms a { cycle cutset } in G if and only if the corresponding set of edges of G∗ forms a { cutset cycle } in G∗. A cycle of length k in either graph corresponds to a cutset with k edges i
n the other. Proof We may consider each component of G separately, so assume G is a connected plane graph containing a cycle C. In the region bounded by the edges in C there is at 42 least one face, in which a vertex of G∗ is located. Let S be the set of all vertices of G∗ that lie inside C and let T be the set of all edges in G∗ that cross the edges in C. Removing the edges in T disconnects the vertices of G∗ in S from the rest. No proper subset of T can have this property, so T is a cutset in G∗. Clearly T con- tains the same number of edges as the cycle C. The converse follows since G∗∗ = G. In Example 2.1.3 there is a cycle C = v1v2v3v1 in G using either of the parallel edges. Take the left-hand one in the drawing; then S = {u2, u3} is the set of vertices inside C. Let T be the set consisting of u1u3 and the two parallel edges u1u2. This is a cutset in G∗ as it disconnects u2 and u3 from u1 and u4, thus disconnecting G∗ into two components, but removing any subset of T would not disconnect G∗. Similarly, the cutset consisting of the edge v3v4 in G corresponds to the cycle that is the loop at u1 in G ∗. Results about plane graphs can be dualized using the correspondences established above. By Proposition 2.3, if a connected simple plane graph has n ≥ 3 vertices and m edges then m ≤ 3n−6. Now G being simple means that it has no loops of multiple edges, i.e. no cycles of length 1 or 2. These correspond to cutsets with 1 or 2 edges in G∗, so the dualized result is: if a connected, 3-edge-connected plane graph has m edges and f faces then m ≤ 3f − 6. Proposition 2.9 A connected plane graph G is bipartite if and only if G∗ is Eulerian. Proof G is bipartite ⇔ G has no cycle of odd length (by Proposition 1.4) ⇔ G∗ has no cutset with an odd number of edges (by Prop. 2.8) ⇔ G∗ has no vertices of odd degree (see Exercises 2.1, Q. 17) ⇔ G∗ is Eulerian (by Proposition 1.9). 43 2.1.4 Maximal planar graphs Definition 2.5 A maximal planar graph is a simple planar graph which would be made non-planar by adding an extra edge between any two non-adjacent vertices. Proposition 2.10 A simple planar graph G is maximal if and only if, in any plane drawing of G, every face has degree 3. In a maximal planar graph with n vertices and m edges, m = 3n− 6. Proof Let G be a simple planar graph drawn in a plane. As G is simple, no face has degree 1 or 2. Suppose there is a face F with degree > 3, so there are vertices v1, . . . , vk inside or on the boundary of F , where k ≥ 4. If a new vertex is placed inside F and joined it to each of v1, . . . , vk, the resulting graph is still planar. If each pair of v1, . . . , vk were adjacent there would be a subgraph isomorphic to K5, which is non-planar. Hence some pair is non-adjacent in G. Joining them with an edge in G, the resulting graph is still planar so G is not maximal planar. Conversely, if every face (including the external face) has degree 3 then 3f = 2m, hence m = 3n−6. Certainly G is simple with at least three vertices. If more edges are added between non-adjacent vertices then the graph is still simple and m > 3n − 6, so it becomes non-planar. Thus G is maximal planar. Proposition 2.10 shows that this is a maximal planar graph. All faces, including the infinite face, are bounded by three edges. n = 11 and m = 27 = 3n− 6. 44 2.1.5 Exercises 1. Make plane drawings of the following graphs: For each of your plane graphs, state the number of faces, find the face degrees and verify Propositions 2.1 and 2.2. 2. Verify Euler’s formula for each of the platonic graphs. 3. A plane connected simple graph has degree sequence 6, 5, 5, 4, 3, 3, 2. Find how many faces it has. 4. G is a 3-regular connected plane graph with 24 vertices. Find the number of faces in G. 5. If a connected graph with n vertices and m edges is face regular of degree r, express m in terms of n and r. 6. Show that a simple connected planar graph with fewer than 12 vertices has at least one vertex whose degree is not more than 4. 7. Let G be a plane graph with n vertices, m edges, f faces and c components. Deduce from Euler’s formula that n−m+ f = c+ 1. 8. The girth of a graph G is the length of the shortest cycle in G. Use Euler’s formula to show that if G is a connected planar graph of girth 5 then m ≤ 5 3 (n− 2). Deduce from this that the Petersen graph is not planar. 9. G is a connected plane graph in which each vertex has degree at least 3, and each face is bounded by either 5 or 6 edges. Show that at least 12 faces are bounded by 5 edges. 10. Three houses are to be connected to three utility supplies: electricity, gas and water. Can this be done in such a way that the supply lines do not cross? 11. Use Kuratowski’s theorem to show that the following graphs are not planar. 45 12. Construct the geometric dual of the following graph G: List the face degrees and the vertex degrees of each of G and G∗. 13. Show that the following two graphs are isomorphic but that their geometric duals are not isomorphic. (There is no need to draw the duals.) 14. Show that if a connected plane graph with n vertices and m edges is isomorphic to its geometric dual, then m = 2(n− 1). 15. Consider the graph G in Example 1.1.1. Without drawing it, state the length of the longest cycle in G∗ and the value of the edge connectivity λ(G∗). 16. Investigate the geometric duals of trees, cycle graphs and wheel graphs. 17. Suppose a graph G has a cutset consisting of an odd number of edges. Show that G has a vertex of odd degree. 18. Determine which of the Platonic graphs are maximal planar graphs. 19. G is a maximal simple planar graph with n vertices and m edges. There are ki vertices of degree i, for i = 1, . . . , n− 1. Show that n−1∑ i=1 (6− i)ki = 12. 20. Show that in a maximal planar graph, every vertex has degree at least 3. Deduce that such a graph has at least four vertices of degree ≤ 5. Hence show that every simple planar graph has at least four vertices of degree ≤ 5. 46 2.2 Graph colourings 2.2.1 The chromatic number and the greedy algorithm Definition 2.6 A colouring (sometimes called a proper colouring) of the ver- tices/edges/faces of a graph is an assignment of colours such that no two distinct adjacent vertices/edges/faces have the same colour. It is a k-colouring if at most k colours are used. If a k-colouring of the vertices exists, the graph is k-colourable. The chromatic number χ(G) is the smallest k ∈ N for which the graph G is k- colourable. For this k, we say that G is k-chromatic. Note that colouring always refers to vertices unless otherwise stated. Terms such as k-edge colouring and k-face colourable can be used for clarity in other cases. Clearly χ(G) cannot be more than the number of vertices of G. χ(Kn) = n, so if G has a subgraph isomorphic to Kn then χ(G) ≥ n. Furthermore χ(G) = 1 if and only if G is a null graph, and χ(G) = 2 if and only if G is bipartite. Graphs with χ(G) = 3 include Cn and Wn for any odd integer n ≥ 3. If G is k-colourable, then clearly so is any subgraph of G. Indeed, if H is a subgraph of G then χ(H) ≤ χ(G). There are various algorithms for colouring graphs. The following method, known as the greedy algorithm, is a simple method for finding a vertex colouring. Label the vertices v1, . . . , vn and the colours 1, 2, . . . For i = 1, . . . , n, assign to vi the lowest- numbered colour that is not already assigned to an adjacent vertex. Certainly χ(G) cannot be greater than the highest-numbered colour that is used, so this method gives an upper bound for the chromatic number. Different orderings of the vertices can require different numbers of colours. Example Consider the following graph (from Exercises 1.3 Question 4). Colouring the vertices in the order v1, . . . , v9, the greedy algorithm assigns colours as follows: v1 : 1, v2 : 2, v3 : 1, v4 : 3, v5 : 4, v6 : 1, v7 : 2, v8 : 2, v9 : 3. Colouring them in the reverse order v9, . . . , v1, we get: 47 v9 : 1, v8 : 2, v7 : 2, v6 : 3, v5 : 2, v4 : 1, v3 : 3, v2 : 4, v1 : 1. We have two 4-colourings. The graph is 4-colourable. Clearly at least 4 colours are neede
d since the graph contains K4, so the graph is 4-chromatic. Recall that ∆(G) denotes the largest degree of any vertex in G. Proposition 2.11 Let G be a simple graph. Then χ(G) ≤ ∆(G) + 1. Proof The result clearly holds for N1, a simple graph with one vertex, for which χ(G) = 1 and ∆(G) = 0. Assume it holds for all graphs with fewer than n vertices. Now let G have n vertices, so G−v has n−1 vertices. Clearly ∆(G−v) ≤ ∆(G), so by the hypothesis χ(G−v) ≤ ∆(G− v) + 1 ≤ ∆(G) + 1. Take a (∆(G) + 1)-colouring of G− v. At most ∆(G) colours are used on the vertices adjacent to v in G, so we can give v a different colour from these to get a (∆(G) + 1)- colouring of G. Thus χ(G) ≤ ∆(G) + 1. The result follows by induction. 2.2.2 The five and four colour theorems Proposition 2.12 (The Five Colour theorem) Every planar graph is 5-colourable. Proof As loops and multiple edges do not affect the adjacency of vertices, it is enough to prove the result for simple graphs. Let G be a simple planar graph with n vertices. The result is obvious for n ≤ 5 as G is then n-colourable. Make the inductive hypothesis that the result holds for all simple planar graphs with fewer then n vertices. By Proposition 2.5, G has a vertex v of degree ≤ 5. Suppose d(v) < 5. By the hypothesis there is a 5-colouring of G − v, in which the vertices which are adjacent to v in G have at most four different colours. There is then another colour available which can be assigned to v, giving a 5-colouring of G. Now suppose d(v) = 5. Let u1, . . . , u5 be the vertices adjacent to v. If each pair out of u1, . . . , u5 were adjacent then G would have K5 as a subgraph, so would not be planar. Thus at least two of these vertices, say ui and uj, are not adjacent. Contract the edges uiv and ujv, so that ui, uj and v are merged into a single vertex w incident to all edges that were incident to ui, uj or v. Replace any resulting parallel 48 edges by single edges. The resulting graph is simple, planar and has fewer than n vertices, so is 5-colourable by the hypothesis. Reinstate v and the two edges that were removed. Assign the colour of w to ui and uj, since they are not adjacent in G. The vertices adjacent to v now have at most four colours, so v can be given a different colour from them to produce a 5-colouring of G. The result follows by induction on n. Proposition 2.13 (The Four Colour theorem) Every planar graph is 4-colourable. The original motivation for graph-colouring problems was the colouring of maps. The question as to whether all maps are 4-colourable was posed by Francis Guthrie to Augustus De Morgan in 1852. There were many flawed attempts at proofs. The Four Colour theorem is generally regarded as having been proved in 1976 by Appel and Haken. Refinements have followed since then. The method involves computer analysis of a large number of cases, so it cannot easily be checked by hand. In the kind of map that we wish to colour, each region (e.g. a country or county) is represented by a single face of a connected planar graph, with one infinite face which is also to be coloured. Vertices of degree 2 may be ignored, as they do not affect the adjacency of faces. 2.2.3 Maps Definition 2.7 A map is a connected plane graph with no bridges. Proposition 2.14 A map has a k-colouring of its faces if and only if its geometric dual has a k-colouring of its vertices. Proof Suppose a map G has a k-colouring of its faces. The geometric dual G∗ is a loopless plane graph. Each face of G contains one vertex of G∗. Faces are adjacent in G if and only if the corresponding vertices are adjacent in G∗, so assigning the colours of the faces of G to the vertices of G∗ gives a k-colouring of these vertices. Similarly, a k-colouring of the vertices of G∗ yields a k-colouring of the faces of G. It follows from Propositions 2.13 and 2.14 that every map is 4-colourable. Proposition 2.15 A map is 2-face-colourable if and only if it is Eulerian. 49 Proof By Proposition 2.14, a map has a 2-colouring of its faces if and only if its dual has a 2-colouring of its vertices, i.e. the dual is bipartite, which by Proposition 2.9 holds if and only if the map is Eulerian. Proposition 2.16 A cubic map is 3-face-colourable if and only if each face has even degree. Proof Suppose a map is cubic, which means that each vertex has degree 3. Then its geo- metric dual is a connected plane graph in which each face (including the infinite one) has degree 3. Such a graph is called a plane triangulation, and is maximal planar by Proposition 2.10. We shall prove that a plane triangulation is 3-colourable if and only if every vertex has even degree. This is equivalent to the proposition, by duality. Suppose G is a plane triangulation and has a vertex v of odd degree. Then v and the adjacent vertices form a wheel Wr, where r is even. This is not 3-colourable, hence nor is G. Now suppose every vertex of a plane triangulation G has even degree. If G is a triangle, it is clearly 3-colourable. Make the inductive hypothesis that the result holds for all plane triangulations with fewer vertices than G, in which every vertex has even degree. By Proposition 2.5, G has a vertex v of degree ≤ 5. As each vertex has even degree, d(v) = 2 or 4. If d(v) = 2 then G−v has a pair of parallel edges. Deleting one of these edges leaves a graph satisfying the inductive hypothesis, which can be 3-coloured. Give v a different colour from each of its neighbours in this colouring, to get a 3-colouring of G. If d(v) = 4, there are four vertices w, x, y, z adjacent to v. As G is planar it does not contain K5 so there is a non-adjacent pair among these vertices, say w and y. If v is at the the centre of a wheel W5, contract the edges vw and vy to get a graph G ′ satisfying the inductive hypothesis, which can be 3-coloured. In G′ there is a wheel subgraph centred on v in which x and z are an even distance apart so they have the same colour, which is different from that of v. Apply this colouring to G, then give the colour of v to both w and y and the third colour to v. We now have a 3-colouring of G. A similar argument applies if v is on the boundary of the infinite face. The result follows by induction. 50 Proposition 2.17 If every cubic map is 4-face-colourable then every map is 4-face- colourable. Proof Let G be a map. Assume it has no vertices of degree 2, as these do not affect colour- ings of the faces. For each vertex v of degree ≥ 4, replace v by a cycle of length d(v) with a vertex incident to each edge that is incident to v. Repeating this as often as necessary, every vertex will eventually have degree 3 so we get a cubic map. Assuming this to have a 4-colouring of its faces, we still have such a colouring when the cycles are replaced by the original vertices. Thus to prove the Four Colour theorem it is only (!) necessary to prove that all cubic maps are 4-colourable. Later we shall see another equivalent condition, in terms of edge colourings. We now consider an application of vertex colourings. 2.2.4 Chromatic polynomials Definition 2.8 Let G be a graph and let k ∈ N. The chromatic polynomial PG(k) is the number of distinct k-colourings of the vertices of G. We must justify calling PG(k) a polynomial: Proposition 2.18 Let G be a simple graph with n vertices and m edges. (i) For each edge e of G, PG(k) = PG−e(k)− PG\e(k). (ii) PG(k) = k n −mkn−1 + n−2∑ r=1 ark r for some a1, . . . , an−2 ∈ Z. Proof (i) Let e be an edge joining vertices v and w. In G and G − e, the numbers of k-colourings in which v and w have different colours are equal. In G − e and G \ e, the numbers of k-colourings in which v and w have the same colour are equal (since they are the same vertex in G \ e). The k-colourings of G − e which are not k-colourings of G are those in which v and w have the same colour, each of which corresponds to a k-colouring of G \ e. Hence PG−e(k) = PG(k) + PG\e(k), giving the required result. (ii) Let G be a simple graph with n vertices. When G has no edges, i.e. G = Nn, then PG(k) = k n so the result holds. 51 Assume it holds for all simple graphs w ith fewer than m edges. Now let G have m edges, so the hypothesis can be applied to G−e and G\e (with parallel edges replaced by single edges), which both have < m edges and n, n− 1 vertices respectively. Thus we can write PG−e(k) = kn − (m− 1)kn−1 + bk−2kn−2 + · · ·+ b1k and PG/e(k) = k n−1 + ck−2kn−2 + ck−3kn−3 + · · ·+ c1k. By (i), PG(k) = PG−e(k)−PG\e(k) = kn−mkn−1+(bk−2−ck−2)kn−2+ · · ·+(b1−c1)k, which is a polynomial of the same form. The result follows by induction on m. Note that PG(k) has constant term 0, so PG(0) = 0 for every graph G. It can further be shown that the terms in PG(k) alternate in sign. χ(G) is the smallest k ∈ N for which PG(k) 6= 0. To find the chromatic polynomial of a graph, we can follow the procedure described in the proof of (i). In this situation, when an edge is contracted any resulting parallel edges are replaced by a single edge. There are some standard results: 1. When G = Nn, PG(k) = k n. 2. When G = Kn, PG(k) = k(k − 1)(k − 2) · · · (k − n+ 1) = k! (k − n)! . 3. When G is a tree with n vertices, PG(k) = k(k − 1)n−1. 4. When G = Cn (for n ≥ 3), PG(k) = (k − 1)n + (−1)n(k − 1). Also, if G is disconnected then PG(k) is the product of the chromatic polynomials of all the components. The chromatic number and polynomial can be applied to scheduling problems. Sup- pose we have a set of events, some of which cannot take place simultaneously. Rep- resent the events by the vertices of a graph G, with edges joining those pairs which must be kept apart. Use different colours for the different time slots. Then χ(G) is the minimum number of separate sessions needed. PG(k) is the number of distinct ways of scheduling the events using up to k sessions. Example Lectures are to be timetabled in Algebra, Calculus, Dynamics, Modelling and Statis- tics. Calculus and Dynamics must be at different times, and neither can take place at the same time as Algebra or Modelling. Also, Modelling and Statistics cannot take place simultaneously. 52 The graph is clearly 3-chromatic, so at least three lecture periods are needed. To find the chromatic polynomial, choose an edge e to remove and contract. Apply PG(k) = PG−e(k)− PG\e(k) to this edge. Taking e = CD we have PG−e(k) = PG1(k) as shown below and PG\e(k) = PP4(k). Then taking e = MS in G1 we have PG1(k) = PG1−e(k)−PG1\e(k) where PG1−e(k) = C4 ∪N1 and PG1\e(k) = C4. Thus PG(k) = kPC4(k)− PC4(k)− PP4(k) = (k − 1)[(k − 1)4 + k − 1]− k(k − 1)3 = (k − 1)2((k − 1)3 + 1− k(k − 1)) = (k − 1)2(k3 − 4k2 + 4k) = k(k − 1)2(k − 2)2. The number of ways of timetabling the lectures in three periods is PG(3) = 12. If four periods are available, it can be done in PG(4) = 144 ways. There are many other results on vertex colourings, such as: Brooks’s theorem: If G is a simple, connected but not complete graph in which ∆(G) ≥ 3, then G is ∆(G)-colourable. Gro¨tzsch’s theorem: If a planar graph G contains no triangles then χ(G) ≤ 3. We next look at edge colourings. 53 2.2.5 Chromatic index and Vizing’s theorem Definition 2.9 Given a graph G, the chromatic index χ′(G) is the smallest k ∈ N for which G is k-edge-colourable. Clearly χ′(G) ≤ |E(G)|. A much better upper bound is given by the following, which shows that there are only two possible values for χ′(G) in any given simple graph. Proposition 2.19 (Vizing’s theorem) Let G be a simple graph. Then χ′(G) is either ∆(G) or ∆(G) + 1. Proof Clearly χ′(G) ≥ ∆(G), so we must show that χ′(G) ≤ ∆(G) + 1. This is clearly true for a graph with one edge, where χ′(G) = ∆(G) = 1. Suppose the result is true for all graphs with fewer edges than G. Let uv be any edge of G. ∆(G − uv) ≤ ∆(G), so by the hypothesis there is an edge colouring of G− uv using colours {1, 2, . . . ,∆(G) + 1}, in which no vertex is incident to edges of all ∆(G) + 1 colours. Say a colour is missing at a vertex if it is not assigned to any edge incident to that vertex. Construct a sequence of edges uv0, uv1, . . . and a sequence of colours c0, c1, . . . as follows: let v0 = v. For i = 0, 1, . . ., let ci be a colour that is missing at vi, and let uvi+1 be an edge (if there is one) that is already assigned colour ci. Stop with k = i when either ck is missing at u, or ck is already used on some edge uvj where j < k. If ck was missing at u, recolour uvi with ci for 0 ≤ i ≤ k to get a (∆(G) + 1)-edge- colouring of G. Otherwise, recolour uvi with ci for 0 ≤ i < j and uncolour uvj. Now ck is missing at both vj and vk. Let c` be a colour that is missing at u. If ck is missing at u, colour uvj with ck. If c` is missing at vj, colour uvj with c`. If c` is missing at vk, colour uvi with ci for j ≤ i < k and colour uvk with c`. (None of the uvi for j ≤ i < k has colour ck or c`.) If none of the above hold, consider the subgraph consisting of all edges coloured ck or c`. The components of this subgraph are paths or cycles. u, vi, vk are the end vertices of paths so they do not all lie in the same component. Take a component that contains exactly one of u, vi, vk and swap ck and c` on each edge in this component. One of the conditions above will now hold, giving a (∆(G) + 1)-edge-colouring of G. The result follows by induction. 54 Proposition 2.20 For all n > 1, χ′(Kn) = n if n is odd and n− 1 if n is even. Proof Each vertex of Kn has degree n− 1, so by Vizing’s theorem χ′(Kn) is n− 1 or n. If n is odd, any n+ 1 2 edges are incident to n + 1 vertices so at least two of these edges are adjacent. Thus at most n− 1 2 edges can have the same colour. Now Kn has n(n− 1) 2 edges, so at least n colours must be used. Thus χ′(Kn) = n. If n is even, we colour the edges of Kn using n− 1 colours as follows. If n = 2 there is one edge, which can be coloured with one colour. For n > 2, let v be any vertex. Then Kn − v is a complete graph Kn−1. As n− 1 is odd, this has an edge-colouring using n− 1 colours. There is such a colouring in which one colour is missing at each vertex and these missing colours are all different, so we can assign them to the edges joining v to the vertices in Kn−1 to give an (n− 1)-edge-colouring of Kn. 2.2.6 Ko¨nig’s theorem Proposition 2.21 (Ko¨nig’s theorem) If G is bipartite (and not necessarily sim- ple) then χ′(G) = ∆(G). Proof The result is clear when G has one edge, as then χ′(G) = ∆(G) = 1. Make the inductive hypothesis that the result is true for all bipartite graphs with fewer edges than G. Delete an edge uv of G to give a bipartite graph G′. Clearly ∆(G′) ≤ ∆(G) so, by hypothesis, there is an edge colouring of G′ using ∆(G) colours. In G′, d(u) < ∆(G) so there is at least one of the ∆(G) colours missing at u, and similarly at v. If the same colour is missing at both u and v, assign this colour to uv to get a ∆(G)-edge colouring of G. Otherwise, suppose colours i and j are missing at u and v respectively. Let Hij be the subgraph of G consisting of v and all edges and vertices that can be reached from v by a path consisting only of edges with colours i and j. These edges must alternate between two sets, so u is not in Hij. Interchanging colours i and j on the edges of Hij will not affect the rest of the colouring. Assigning colour i to uv now gives a ∆(G)-edge colouring of G. The result follows by induction. 55 Proposition 2.22 Every map is 4-face-colourable if and only if χ′(G) = 3 for every cubic map G. Proof By Proposition 2.17, every map is 4-face-colourable if and only if every cubic map is 4-face-colourable. Suppose G is a cubic map whose faces can be coloured with four colours α = (0, 0), β = (0, 1), γ = (1, 0), δ = (1, 1). Colour each edge e of G with the sum (mod 2) of the colours of the faces either side of e, e.g. if e lies between faces coloured β and δ then e will be coloured with (0, 1) + (1, 1) = (1, 0) = γ. Now each edge is coloured with one of β, γ or δ, since no two distinct colours have sum α. The three faces that meet at each vertex have different colours. The sums of these pairs are different, so adjacent edges have different colours. Thus we have a 3-edge-colouring of G. Clearly two colours are not enough, so χ′(G) = 3. Conversely, suppose G is a cubic map and we have a 3-edge-colouring using colours α, β, γ. Edges of all three colours meet at each vertex. Consider the subgraph of G consisting of those edges coloured α or β. This is 2-regular, hence each component is Eulerian, so its faces can be coloured using two colours: call them 0 and 1. The same can be done with the subgraph of G consisting of those edges coloured α or γ. These colourings give, for each face, an ordered pair (x, y), where x, y ∈ {0, 1}. For two adjacent faces, either the x values or the y values (or both) are different, so (0, 0), (0, 1), (1, 0), (1, 1) give a 4-colouring of the faces of G. 56 2.2.7 Exercises 1. Consider the graph G in the first diagram in Example 2.2.4 (top of Page 53). Apply the greedy algorithm to allocate colours 1, 2, 3, . . . to the vertices in the orders (i) A,C,D,M, S, (ii) A,C,D, S,M . State the value of χ(G). 2. v is a vertex of a graph G, such that d(v) < k. Show that if G−v is k-colourable then G is k-colourable. 3. G is an r-regular simple graph with n vertices. Prove that χ(G) ≥ n n− r . 4. Let α(G) denote the number of vertices in the largest independent set of vertices in a graph G with n vertices. Show that α(G)χ(G) ≥ n. 5. Find the minimum number of colours needed for a proper colouring of the faces of each of the Platonic graphs. 6. Show that if G is a k-colourable simple graph with n vertices then G has a vertex of degree less than or equal to ⌊ n ( 1− 1 k )⌋ . 7. Show that if G is not a connected graph then the coefficient of k in PG(k) is zero. 8. Using the standard result for the chromatic polynomial of Cn, find the chromatic polynomial of the wheel graph Wn. 9. Find the chromatic polynomials of the six connected simple graphs with four vertices. Hence find the number of ways of 4-colouring each of these graphs. 10. An examination schedule is to be drawn up for a set of five modules, A to E. The table below shows the exams which may not be scheduled at the same time (marked with a ∗). Find the minimum number of periods needed to schedule all five exams, and the number of ways of scheduling them using this many periods. A B C D E A ∗ ∗ ∗ ∗ B ∗ ∗ C ∗ ∗ ∗ D ∗ ∗ ∗ E ∗ ∗ 57 11. Use any of the results proved or stated in the notes to find the chromatic index of (i) Kr,s (where r ≤ s), (ii) the graphs of the tetrahedron and cube (as on Page 2). 12. Show that every 3-regular Hamiltonian simple graph is 3-edge-colourable. 58 2.3 Matchings and flows 2.3.1 Menger’s theorem Definition 2.10 Let A and B be subsets of the vertex set of a graph G. An A,B path in G is either a path between a vertex in A and a vertex in B, or a single vertex of A ∩B. A set of paths in G is disjoint if no two of them have any vertices (and hence edges) in common. A set S of vertices is called an A,B separator if every A,B path includes a vertex in S. Proposition 2.23 (Menger’s theorem) Let A and B be sets of vertices in a graph G. Then the maximum number of disjoint A,B paths in G is equal to the minimum order of an A,B separator. Proof The result is clear if G has no edges, as both numbers are then equal to |A ∩ B| (which equals 0 if A and B have no vertices in common). Now assume G has at least one edge and make the inductive hypothesis that the result holds for all graphs with fewer edges than G. Let s be the minimum order of an A,B separator in G. Clearly there cannot be more than s disjoint A,B paths. We must show that s such paths exist. Let e = uv be any edge of G. Contract the edge e to get the graph G \ e in which u and v become a single vertex w, which is regarded as being in A if u or v is in A and in B if u or v is in B. Let S be an A,B separator of minimal order in G \ e, so |S| ∈ {s, s− 1}. If |S| = s, which is certainly the case if w /∈ S, then by the hypothesis there are s disjoint A,B paths in G \ e and hence in G. If |S| = s − 1 then w ∈ S. Any A,B path passing through u or v in G would pass through w in G \ e. Thus the vertices in S other than w, together with u and v, form an A,B separator X of order s in G. Each A,X separator or X,B separator in G − e is an A,B separator in G, so has order at least s. Thus by the inductive hypothesis G − e contains s disjoint A,X paths which join vertices in A to the s vertices in X, and s disjoint X,B paths which join the s vertices in X to vertices in B. An A,X path and an X,B path in G can intersect only in X, as otherwise G would contain an A,B path entirely outside X. Thus combining each of s A,X paths with each of s X,B paths gives s disjoint A,B paths in G, as required. 59 The result follows by induction on the number of edges of G. It follows from Menger’s theorem (see Exercises) that given any two non-adjacent vertices u and v in a graph, the minimum number of vertices in a u, v-separating set equals the maximum number of paths between u and v which have no vertices in common except u and v. Definition 2.11 Let G(U,W ) be a bipartite graph. A (complete) matching from U to W is a one-to-one correspondence between V (U) and a subset of V (W ), such that corresponding vertices are adjacent. 2.3.2 Hall’s theorem Proposition 2.24 (Hall’s theorem) Let G(U,W ) be a bipartite graph. For each subset S of U , let θ(S) be the set of all vertices of W that are adjacent to at least one vertex in S. Then there is a matching from U to W if and only if |θ(S)| ≥ |S| for every subset S of U . Proof It is clear that if a matching exists then |θ(S)| ≥ |S| for all S ⊂ U . For the converse, assume |θ(S)| ≥ |S| for each S ⊂ U and let X be a U,W separator consisting of a subset S of U and a subset T of V . Then no vertex in U \ S is adjacent to a vertex in V \ T , so θ(U \ S) ⊂ T . Thus |U \ S| ≤ |θ(U \ S)| ≤ |T |, so |X| = |S|+ |T | ≥ |S|+ |U \ S| = |U |. Hence by Menger’s theorem, there are at least |U | vertex-disjoint U,W paths in G. Each of these is a single edge, giving the required matching. Hall’s theorem is often called the marriage theorem: given sets of men and women, each of the r women can marry a man she knows if and only if, for k = 1, . . . , r, every set of k women collectively knows at least k men. This condition is clearly necessary; the theorem shows that it is also sufficient. Another interpretation of the theorem uses the following idea. 60 2.3.3 Transversals Definition 2.12 Let E be a non-empty finite set and let F = (X1, . . . , Xr) be a family of non-empty subsets of E (not necessarily distinct). A transversal (or system of distinct representatives) of F is a set of r distinct elements of E consisting of one element from each of X1, . . . , Xr. Clearly a transversal exists if and only if there is a matching from F to E, so Hall’s theorem can be restated as follows: F has a transversal if and only if, for each of k = 1, . . . , r, the union of any k of X1, . . . , Xr has order ≥ k. Example Let E = {a, b, c, d, e, f},F = (X1, . . . , X5) whereX1 = {a, b, c, d}, X2 = {a, c, d, e}, X3 = {a, f}, X4 = {a, f}, X5 = {a, c, e, f}. Then F has transversals. For example, (d, c, a, f, e) is a transversal of F . Example Let E = {1, 2, 3, 4},F = (X1, X2, X3, X4) where X1 = {1, 2, 3, 4}, X2 = {3, 4}, X3 = {3}, X4 = {4}. |X2 ∪X3 ∪X4| = 2 < 3 so F has no transversal. 2.3.4 Networks Definition 2.13 A network is a directed graph in which a positive capacity c(e) is assigned to each arc e. For any vertex v, the in-degree din(v) and out-degree dout(v) are the total capacities of all arcs leading into v and out of v, respectively. Example In this network, din(s) = 0, dout(s) = 10, din(u) = dout(u) = 6, din(v) = dout(v) = 5, din(t) = 10, dout(t) = 0. Notice that the sum of the in-degrees, 21, equals the sum of the out-degrees. 61 Definition 2.14 In a connected network, a source (or initial vertex) s has din(s) = 0, dout(s) > 0. A sink (or terminal vertex) t has din(t) > 0, dout(t) = 0. A flow in a network is a function f from the set of arcs to the n
on-negative real numbers such that f(e) ≤ c(e) for each arc e. At each vertex v, the in-flow fin(v) is the sum of the flows in all arcs leading into v and the out-flow fout(v) is the sum of the flows in all arcs leading out of v. The in-flow and out-flow must be equal at each v /∈ {s, t}. The value of the flow is fout(s), or equivalently fin(t). An arc is saturated if the flow in it is equal to its capacity. A cut is a set of arcs whose removal leaves no path from s to t, such that no proper subset has this property. The capacity of a cut is the sum of the capacities in all those arcs which cross the cut from the side containing s to the side containing t. There are several alternative forms of Menger’s theorem. One of these states that the maximum number of arc-disjoint paths from a vertex u to a vertex v in a digraph is equal to the minimum number of arcs in a u, v-disconnecting set, i.e. a set of arcs whose removal leaves no path from u to v. We use this to prove: Proposition 2.25 In a network with a source and sink, the maximum value of a flow is equal to the minimum capacity of a cut. Proof Clearly the maximum flow is less than or equal to the minimum capacity of any cut. Assume the capacities are integers. The network can be represented by a digraph D in which the number of arcs from vi to vj equals the capacity of vivj. The maximum flow is then equal to the number of arc-disjoint paths in D from the source s to the sink t. By the version of Menger’s theorem stated above this equals the smallest number of arcs in an s, t-disconnecting set in D, which in turn represents the minimum capacity of any cut. If the capacities are rational, they can be multiplied by a suitable integer to make them all integers. This will not affect their comparative sizes, so the result for inte- gers can be applied. Irrational flows (which seldom occur) may be approximated by rationals to any required degree of accuracy. There are algorithms for finding the maximum flow in a network. If we can find, by inspection or otherwise, a flow and a cut that have the same value then they must be respectively maximal and minimal. The flow consists of a value for each arc, less than or equal to the capacity of the arc, such that the flows into and out of each vertex are equal. 62 Example The left-hand diagram shows a network with the capacities shown on the arcs. The vertical line shows a cut of value 20. The right-hand diagram shows a flow of 20. The circled values are on saturated edges. This must be the maximum flow from s to t, as we have found a cut of equal value. 63 2.3.5 Exercises 1. u and w are vertices of a connected graph G. k is the order of the smallest set S ⊂ V (G)\{u,w} such that there is no path from u to w in G−S. Use Menger’s theorem to show that there are at most k paths from u to w in G which are internally disjoint, i.e. they have no vertices except u and w in common. 2. u is a vertex of a connected, k-connected graph G. U is the set of all neighbours of u and W is a set of at least k vertices of G, other than u. Use Menger’s theorem to show that there are k paths from u to W which have no vertices except u in common. 3. Let k ≥ 2. Use the previous question to show that every k-connected graph with at least 2k vertices contains a cycle of length at least 2k. 4. Wilson (link on SurreyLearn) Exercises 25.1, 25.3, 26.1 (omit partial transver- sals), 26.4, 29.1. 64 Chapter 3 Graphs and matrices 3.1 Adjacency matrix Definition 3.1 Let v1, . . . , vn be the vertices of a graph G. The adjacency matrix of G, relative to the given labelling, is the n × n matrix A with (i, j) entry equal to the number of edges joining vi to vj. Clearly A is symmetric. For a simple graph, aij = 1 if vi and vj are adjacent, and 0 otherwise. If G has loops at vi then each loop contributes 1 to the (i, i) entry. Labelling the vertices of G differently will permute the rows, and the columns cor- respondingly, so that the resulting matrix A′ is similar to A, i.e. there is a matrix P such that A′ = P−1AP. P is a permutation matrix, obtained from the n× n identity matrix In by applying the same permutation to its columns. Any such matrix P is an orthogonal matrix, i.e. P−1 = Pt. The adjacency matrix can also be defined when G is a digraph. In that case the (i, j) entry is the number of arcs from vi to vj and the matrix is not necessarily symmetric. Example The adjacency matrix A =  1 1 1 0 1 0 1 1 1 1 0 2 0 1 2 0  represents the following graph relative to the vertex labelling (v1, v2, v3, v4). 65 v3 v4 v2v1 e1 e2 e3 e4 e5 e6 e7 If u1 = v2, u2 = v3, u3 = v4, u4 = v1 then relative to (u1, u2, u3, u4) the graph has adjacency matrix A′ =  0 1 1 1 1 0 2 1 1 2 0 0 1 1 0 1 . We have A′ = P−1AP where P =  0 0 0 1 1 0 0 0 0 1 0 0 0 0 1 0 , the identity matrix I4 with its columns permuted in the order 2, 3, 4, 1. Proposition 3.1 Let A be the adjacency matrix of a graph G with n vertices. For any r ∈ N, the (i, j) entry of Ar is the number of walks in G of length r from vi to vj. Proof The result is clear when r = 1, by the definition of A. Assume the statement is true for r = k. Let cij be the (i, j) entry of A k. Ak+1 = AkA, so the (i, j) entry of Ak+1 is n∑` =1 ci`a`j. By assumption ci` is the number of walks of length k from vi to v` and a`j is the number of edges joining v` to vj, so the sum is the number of walks of length k + 1 from vi to vj. Thus the result holds when r = k + 1, so by induction it is true for all r ∈ N. Example For the graph in Example 3.1, A2 =  3 2 2 3 2 3 3 2 2 3 6 1 3 2 1 5 . Thus there are 3 walks of length 2 from v1 to v1. These are v1v2v1, v1v3v1, and round the loop twice. As the graph is undirected, traversing the loop in different directions does not give distinct walks. 66 There are two walks of length 2 from v1 to v2, namely v1v3v2 and v1v1v2, the latter being the loop (in either direction) followed by the edge v1v2. It is clear that a graph is disconnected, with c components, if and only if its vertices can be ordered such that its adjacency matrix has the form  A1 . . . Ac , all entries outside the diagonal blocks being zero. This matrix is called the direct sum or diagonal sum A1 ⊕ · · ·⊕ Ac. From Year 1 Linear Algebra, every real symmetric matrix A is diagonalisable; indeed, there is an orthogonal matrix P such that PtAP is a diagonal matrix. This implies that the algebraic and geometric multiplicities of any eigenvalue are equal, i.e. the number of times the eigenvalue occurs as a root of the characteristic equation equals the dimension of the associated eigenspace. Thus we can just refer to the multiplicity of an eigenvalue. The set of all eigenvalues of a matrix is called its spectrum. We say the spectrum is symmetric if whenever λ is an eigenvalue, −λ is also an eigenvalue with the same multiplicity. Proposition 3.2 A graph is bipartite if and only if the spectrum of its adjacency matrix is symmetric. Proof A bipartite graph G(U,W ) can be labelled such that its adjacency matrix A has the form ( O B Bt O ) , where B is a p× q matrix, p = |U | and q = |W |. Let x be an eigenvector of A, associated with the eigenvalue λ, so Ax = λx. We can write x as ( y z ) where y ∈ Rp, z ∈ Rq. Thus Bz = λy and Bty = λz, so A ( −y z ) = ( Bz −Bty ) = ( λy −λz ) = −λ ( −y z ) . Hence for every eigenvalue λ there is an eigenvalue −λ. The sum of the eigenvalues is the trace of A, which equals 0 as a bipartite graph has no loops, so λ and −λ have the same multiplicity. Thus the spectrum of A is symmetric. Conversely, suppose the spectrum of A is symmetric. The eigenvalues of Ar are the rth powers of those of A, so for any odd r ∈ N the trace of Ar is 0. As the entries are non-negative, it follows that each diagonal entry of Ar is 0. 67 Thus by Proposition 3.1 there are no walks of odd length from any vertex to itself, i.e. no closed walks of odd length in G. In particular there are no odd cycles, so G is bipartite. Let A be a symmetric n× n real matrix, x a column vec
tor in Rn, and q(x) = xtAx. Recall from Linear Algebra that q(x) is called a real quadratic form. A has eigenvalues λ1 ≥ λ2 ≥ · · · ≥ λn, associated with mutually orthogonal eigenvec- tors v1, . . . ,vn which we can assume have been normalised, i.e. they are unit vectors. Letting P be the matrix with these vectors as its columns, we have P−1AP = D, the diagonal matrix with λ1, . . . , λn on its main diagonal. P is orthogonal, so P −1 = Pt. {v1, . . . ,vn} is a basis for Rn, so any vector x ∈ Rn can be written as c1v1+· · ·+cnvn. Let c = (c1 · · · cn)t, so x = Pc. Then xtAx = (Pc)tAPc = ctPtAPc = ctDc = λ1c 2 1 + · · ·+ λnc2n. Suppose x is a unit vector. As P is orthogonal, |Pc| = |c|, so |c| = |x| = 1, hence c21 + · · ·+ c2n = 1. Thus xtAx ≤ λ1c21 + · · ·+ λ1c2n = λ1 and xtAx ≥ λnc21 + · · ·+ λnc2n = λn. Now xtAx = λ1 when x = v1 and x tAx = λn when x = vn, giving the following result which you may have met in Operations Research and Optimisation: Proposition 3.3 Let A be a symmetric real matrix and let q(x) = xtAx. The maximum value of q(x) subject to |x| = 1 is equal to the largest eigenvalue of A, and occurs when x is a corresponding unit eigenvector. The minimum value of q(x) subject to |x| = 1 is equal to the smallest eigenvalue of A, and occurs when x is a corresponding unit eigenvector. We now apply this to some results in Graph Theory. 68 Proposition 3.4 Let H be a subgraph of a simple graph G with vertices v1, . . . , vn. Let λ1, µ1 be the largest eigenvalues of the adjacency matrices AG, AH of G and H respectively. Then µ1 ≤ λ1. Proof If V (H) does not include all the vertices of G, replace H by its union with these isolated vertices; this simply adds some zero rows and columns to AH and does not affect its eigenvalues. Now AG and AH have the same dimensions. All their entries are either 0 or 1. Letting x = (x1 · · · xn)t be a unit eigenvector of AH associated with µ1, we have µ1 = x tAHx = 2 ( ∑ vivj∈E(H) xixj ) ≤ 2 ( ∑ vivj∈E(G) xixj ) = xtAGx By Proposition 3.3, xtAGx ≤ λ1, so µ1 ≤ λ1. Proposition 3.5 Let λ1 be the largest eigenvalue of the adjacency matrix of a simple graph G. Then δ(G) ≤ λ1 ≤ ∆(G) and χ(G) ≤ 1 + λ1. Proof Let u = (u1 · · · un)t be a unit eigenvector of A associated with λ1, so Au = λ1u and |u| = 1. As u 6= 0, we can assume u has at least one positive entry. Let uk be the largest positive entry of u. Then λ1uk = kth entry of Au = n∑ j=1 akjuj ≤ n∑ j=1 akjuk = d(vk)uk ≤ ∆(G)uk, so λ1 ≤ ∆(G). Let 1 be the vector in Rn whose entries are all 1, so 1√ n 1 is a unit vector. Then λ1 = max|x|=1 xtAx ≥ 1√ n 1tA 1√ n 1 = 1 n 1tA1 = 1 n n∑ i=1 n∑ j=1 aij = 1 n ∑ v∈V (G) d(v) ≥ δ(G), so λ1 ≥ δ(G). Now define subgraphs Gi as follows: G1 = G and for i = 1, . . . , n− 1, Gi+1 = Gi− vi where vi is a vertex of smallest degree in Gi. Then Gn is a single vertex vn. χ(Gn) = 1 and λ1 ≥ 0, so Gn is (1 + λ1)-colourable. Assume that Gi+1 is (1 + λ1)-colourable. The degree of vi in Gi is less than or equal to the largest eigenvalue of A(Gi), which is less than or equal to λ1 by Proposition 3.4. Hence vi has at most λ1 neighbours in Gi. These are all in Gi+1, so there is at least one of the 1 + λ1 colours available to colour vi differently from its neighbours. Thus there is a vertex-colouring of Gi with these colours. The result for G follows by induction. 69 3.2 Incidence matrix Definition 3.2 Let G be a graph with vertices v1, . . . , vn and edges e1, . . . , em. The (vertex-edge) incidence matrix of G is the n × m matrix B with (i, j) entry equal to 1 if vi is incident to ej and 0 otherwise. Clearly this matrix depends on the ordering of both the vertices and the edges. Example For the graph in Example 3.1, relative to (v1, . . . , v4) and (e1, . . . , e6), the incidence matrix of G is B =  1 1 1 0 0 0 0 0 1 0 1 1 0 0 0 0 1 1 0 1 1 0 0 0 0 1 1 1 . We see that a column corresponding to a loop contains a single 1, while any other column has 1 in exactly two positions, in the rows corresponding to its two ends. Different orderings of the vertices and edges will permute the rows and columns. A vector x of length m can represent a set Ex of edges by letting the jth entry be 1 if ej is in the set and 0 otherwise. For example, if there are seven edges then (1, 1, 0, 1, 0, 1, 0) represents {e1, e2, e4, e6}. Row i of the incidence matrix is a vector which represents the set of edges that are incident to vi. Writing x as a column vector, Bx is the column vector whose ith entry is the number of edges in Ex that are incident to vertex vi. With B as in the example above, taking x = (1 1 0 1 0 1 0)t, we find Bx = (2 2 2 1)t. This shows that, from the set {e1, e2, e4, e6}, two edges are incident to each of v1, v2, v3 and one edge is incident to v4. BBt is the n×n matrix whose (i, j) entry is the number of edges that are incident to both vi and vj. Every entry of the incidence matrix B is 0 or 1, so we can regard B as a matrix over the field F2 of integers modulo 2; that is, F2 = {0, 1} where 1+1 = 0. A vector which represents a set of edges has entries 0 or 1, so can be regarded as a vector over F2. Recall that the null space of B, Null(B), is the set of all vectors x such that Bx = 0. The row space of B, Row(B) is the set of all linear combinations of the rows of B. Null(B) and Row(B) are subspaces of F2m. Proposition 3.6 Let B be the incidence matrix of a graph G with no loops. Regard B as a matrix over F2. 70 A vector x ∈ F2m is in Null(B) if and only if it represents a union of one or more edge-disjoint cycles in G. A vector x ∈ F2m is in Row(B) if and only if it represents a union of one or more disjoint cutsets in G. Proof The ith entry of Bx is the number (mod 2) of edges incident to vi in the set Ex represented by x. This is 0 for each i if and only if every vertex of G is incident to an even number (possibly 0) of edges in Ex. By Proposition 1.9, this holds if and only if Ex can be partitioned into edge-disjoint cycles. Let S = {vi1 , . . . , vir} be a set of r vertices of G. The sum (modulo 2) of rows i1, . . . , ir of B is a vector with jth entry 1 if ej is incident to an odd number of the vertices in S, and 0 otherwise. This vector represents the set of all edges that are incident to exactly one vertex in S, so deleting these edges will disconnect the subgraph induced by S from the rest of the graph. This is the case if and only if they represent a union of one or more disjoint cutsets. Definition 3.3 With G and B as above, Null(B) is the cycle space of G. Its di- mension is the cycle rank or nullity, γ(G). Row(B) is the cutset space of G. Its dimension is the cutset rank, ξ(G). The cycle rank and cutset rank of G are respectively the nullity and rank of the incidence matrix B. Recall that the nullity and rank of a matrix add up to the number of columns. Assuming G has no loops, the sum of the rows of B is 0. If G is connected and one row is deleted, the remaining rows form a linearly independent set so ξ(G) = n − 1 and γ(G) = m− n+ 1. If G has c components with n1, . . . , nc vertices then ni − 1 out of each set of ni rows are linearly independent, so ξ(G) = n− c and γ(G) = m−n+ c. Thus the definitions here are consistent with those in Definition 1.19. Consider the graph in Example 3.1, excluding the loop e1. The incidence matrix is now B =  1 1 0 0 0 0 1 0 1 1 0 0 0 1 1 0 1 1 0 0 0 1 1 1 . We have ξ(G) = 4−1 = 3 and γ(G) = 6−4+1 = 3. Row(B) is spanned over F2 by any three rows of B, which form a basis for the cutset space. 71 Null(B) is spanned over F2 by {(0, 1, 1, 1, 0, 0, 0), (0, 1, 1, 0, 1, 1, 0), (0, 1, 1, 0, 1, 0, 1)}. These represent the cycles e2e3e4, e2e5e6e3, e2e5e7e3. These form a basis for the cycle space, sometimes referred to as a fundamental set of cycles. 3.3 Degree and Laplacian matrices Definition 3.4 Let G be a loopless graph with vertices v1, . . . , vn and adjacency ma- trix A. The degree matrix of G is the n × n diagonal matrix D with (i, i) entry d(vi) and all other entries 0. Th
e Laplacian matrix of G is the n× n matrix L = D− A. L is a real symmetric matrix, so its eigenvalues are real. It is clear from the definition that the sum of the entries in each row or column of L is 0, so if 1 is the vector whose entries are all 1 then L1 = 0. Hence 0 is an eigenvalue of L, which is singular. Let C be the n×m signed incidence matrix of G, which is formed by changing a single 1 to −1 in each column. It does not matter which; we normally change the ‘lower’ entry to −1. The (i, j) entry of CCt is (row i of C) . (row j of C). This equals d(vi) if i = j and −aij otherwise. Thus CCt = D − A = L. Example For the graphG shown here, relative to the ordering (v1, . . . , v5), A =  0 1 0 1 0 1 0 1 1 0 0 1 0 0 1 1 1 0 0 1 0 0 1 1 0 , D =  2 0 0 0 0 0 3 0 0 0 0 0 2 0 0 0 0 0 3 0 0 0 0 0 2  so L =  2 −1 0 −1 0 −1 3 −1 −1 0 0 −1 2 0 −1 −1 −1 0 3 −1 0 0 −1 −1 2 . Let C =  1 0 1 0 0 0 −1 1 0 1 0 0 0 −1 0 0 1 0 0 0 −1 −1 0 1 0 0 0 0 −1 −1 . Then CCt =  2 −1 0 −1 0 −1 3 −1 −1 0 0 −1 2 0 −1 −1 −1 0 3 −1 0 0 −1 −1 2  = L. 72 Note that if x = (x1 · · · xn)t then Ctx has an entry xi − xj for each edge vivj of G, so xtLx = xtCCtx = (Ctx)t(Ctx) = ∑ vivj∈E(G) (xi − xj)2 ≥ 0. If Lx = λx then 0 ≤ xtLx = λ|x|2, so λ ≥ 0. Proposition 3.7 Let G be a loopless graph. The number of components of G equals the multiplicity of 0 as an eigenvalue of the Laplacian matrix of G. Proof Let G have c components G1, . . . , Gc. For j = 1, . . . , c, let uj be the column vector with ith entry 1 if vi ∈ Gj and 0 otherwise. Then Luj = 0, and uj . uk = 0 for j 6= k. Mutually orthogonal vectors form a linearly independent set, so there are at least c distinct eigenvectors associated with the eigenvalue 0. Let x = (x1, . . . , xn) be any eigenvector of L associated with 0. Lx = 0 so 0 = x tLx =∑ vivj∈E(G) (xi−xj)2. Thus xi = xj whenever vi and vj are in the same component of G, so x is a linear combination of the c vectors uj defined above. Hence the dimension of the eigenspace for 0 (i.e. the multiplicity of the eigenvalue 0) is exactly c. It follows that if L has (not necessarily distinct) eigenvalues 0 = λ1 ≤ λ2 ≤ · · · then G is disconnected if and only if λ2 = 0. Recall that for each entry aij of an n×n matrix A, its minor Mij(A) is the determinant of the (n− 1)× (n− 1) matrix obtained by deleting row i and column j of A. 3.4 Matrix tree theorem Proposition 3.8 (The matrix tree theorem) The number of distinct labelled spanning trees of a connected loopless graph G is equal to the minor of any entry on the main diagonal of the Laplacian of G. Proof The result is true for a graph with one edge, for which the Laplacian is ( 1 −1 −1 1 ) and there is one spanning tree. Make the inductive hypothesis that it is true for any connected loopless graph with fewer edges than G. Let e = vivj be any edge of G. The spanning trees of G which do not include e are the spanning trees of G− e. The spanning trees of G which do include e correspond 73 to spanning trees of G \ e. Thus the number t(G) of labelled spanning trees of G satisfies t(G) = t(G− e) + t(G \ e). L(G− e) is obtained from L(G) as follows: the (i, i) and (j, j) entries decrease by 1, while the (i, j) and (j, i) entries increase by 1. Expanding Mii(L(G−e)) by row j, all the terms are the same as in Mii(L(G)) except for the first term, which decreases by the determinant of the matrix obtained by deleting rows i and j and columns i and j of L(G). This is the minor of the ith diagonal entry of L(G \ e), since the other rows and columns are not affected by contracting e. Thus Mii(L(G)) = Mii(L(G− e)) +Mii(L(G \ e)). G− e and G \ e have fewer edges than G so by the inductive hypothesis, t(G− e) = Mii(L(G− e)) and t(G \ e) = Mkk(L(G \ e)). The result follows by induction. To illustrate the proof, consider the following graph G and let e = v1v4. L(G) =  2 0 −1 −1 0 0 1 −1 0 0 −1 −1 3 0 −1 −1 0 0 2 −1 0 0 −1 −1 2 , L(G − e) =  1 0 −1 0 0 0 1 −1 0 0 −1 −1 3 0 −1 0 0 0 1 −1 0 0 −1 −1 2 , L(G \ e) =  2 0 −1 −1 0 1 −1 0 −1 −1 3 −1 −1 0 −1 2 . M11(L(G)) = ∣∣∣∣∣∣∣∣ 1 −1 0 0 −1 3 0 −1 0 0 2 −1 0 −1 −1 2 ∣∣∣∣∣∣∣∣ and M11(L(G− e)) = ∣∣∣∣∣∣∣∣ 1 −1 0 0 −1 3 0 −1 0 0 1 −1 0 −1 −1 2 ∣∣∣∣∣∣∣∣. Ex- panding these by the last row, the only difference is in the minor of the entry which changes from 2 to 1. This minor equals ∣∣∣∣∣∣ 1 −1 0 −1 3 −1 0 −1 2 ∣∣∣∣∣∣, which equals M11(L(G\e)). It can be shown more generally that the number of spanning trees equals the modulus of the minor of any entry of the Laplacian. 74 Example The graph in Example 3.1, ignoring the loop e1, has Laplacian matrix L =  2 −1 −1 0 −1 3 −1 −1 1 −1 4 −2 0 −1 −2 3 . Find any 3× 3 minor of L, e.g. M44 = ∣∣∣∣∣∣ 2 −1 −1 −1 3 −1 −1 −1 4 ∣∣∣∣∣∣ = 2(11) + 1(−5)− 1(4) = 13, or M32 = ∣∣∣∣∣∣ 2 −1 0 −1 −1 −1 0 −2 3 ∣∣∣∣∣∣ = 2(−5) + 1(−3) = −13. Thus there are 13 labelled spanning trees of this graph. If a graph is planar and has fewer faces than vertices, it can be easier to use the following: Proposition 3.9 A connected plane graph G and its geometric dual G∗ (excluding any loops) have the same number of distinct labelled spanning trees. Proof Let G have n vertices, m edges and f faces. Let T be a spanning tree of G, so T has n − 1 edges. Let H be the subgraph of G∗ consisting of all edges corresponding to those not in T , except for any loops (which can never form part of a spanning tree). A cycle in H is a cycle in G∗ formed from edges in H. This corresponds to a cutset in G formed from edges not in T . But every cutset of G must include an edge of T . Hence H contains no cycles. Now G∗ has f vertices and the number of edges of H is m−(n−1) = f−2+1 = f−1. Thus H is a spanning tree of G∗. As G∗∗ = G, the same reasoning can be applied to obtain a spanning tree of G from one of G∗. There is thus a one-to-one correspondence between the spanning trees of G and those of G∗, so the numbers of them are the same. Example For the graph in Example 3.3, the geometric dual has Laplacian matrix  3 −1 −2−1 4 −3 −2 −3 5 . (Remember that the entries in each row and column must add up to 0.) Any 2 × 2 minor of this matrix has modulus 11, so the dual, and hence also the original graph, has 11 distinct labelled spanning trees. 75 Definition 3.5 Let e1, . . . , em be the edges of a graph G. The edge-adjacency matrix of G is the m×m matrix in which the (i, j) entry, for i 6= j, is equal to the number of vertices (0, 1 or 2) at which ei and ej meet. The (i, i) entry is 1 if ei is a loop and 0 otherwise. Example The edge-adjacency matrix of this graph, relative to the labelling (e1, . . . , e5), is 1 1 1 0 0 1 0 1 1 1 1 1 0 1 1 0 1 1 0 2 0 1 1 2 0 . The edge-adjacency matrix of a graph can be used to construct another graph of which it is the adjacency matrix. For simple graphs, this is easily described as follows: Definition 3.6 Let G be a simple graph with edges e1, . . . , em. The line graph of G, denoted by Λ(G), has vertices v1, . . . , vm, such that vi and vj are adjacent in Λ(G) if and only if ei and ej are adjacent edges in G. Example The simple graph G below has edge-adjacency matrix  0 1 1 0 1 0 1 1 1 1 0 1 0 1 1 0 . This is the (vertex) adjacency matrix of its line graph Λ(G). 76 3.5 Exercises 1. Write down the adjacency matrices of the graphs in Example 1.1.1 and Exercises 2.1 Question 1 (a), relative to the given labellings of the vertices. For the graph in Example 1.1
.1, square its adjacency matrix and identify all the walks of length 2 from v1 to v3. 2. A is the adjacency matrix of a graph G. (a) State what the entries of A + A2 + · · · + Ar represent. (b) Suppose G is simple. Show that the trace of A is 0 and the trace of A2 is twice the number of edges of G. What does tr(A3) represent? 3. Let G be an r-regular simple graph with n vertices. Show that 1 (the vector whose entries are all 1) is an eigenvector of the adjacency matrix of G and find the associated eigenvalue. Show also that the adjacency and Laplacian matrices of G have the same eigenvectors. 4. Let B be the incidence matrix of a tree. Regarding B as a matrix over F2, identify the null space of B. 5. For the graph in Example 3.3, find bases for the cutset space and cycle space. 6. Write down the incidence matrix of the graph G in Example 1.1.1, relative to the orderings (e1, . . . , e10) and (v1, v2, v3, v4). For the same graph G, find the Laplacian matrix of G− e1. Also give a matrix C such that CCt = L(G− e1). 7. Find the Laplacian matrices of the cycle graph C4 (with vertices labelled in order around the cycle) and the path graph P2. Show that if ( a b ) is an eigenvector of L(P2) then  a b b a  is an eigenvector of L(C4). 8. Use the matrix tree theorem to find the number of labelled spanning trees of (i) K3, (ii) the graph in Example 3.3. 9. A vector y of length n can represent a set Vy of vertices by letting the ith entry be 1 if vi is in the set and 0 otherwise. For example, if there are four vertices then (1, 1, 0, 1) represents {v1, v2, v4}. 77 (a) Give interpretations of: (i) column j of the incidence matrix, (ii) y1 . y2, (iii) the ith entry of Bty, (iv) the (i, j) entry of BtB. (b) If G is a loopless graph, how is the edge-adjacency matrix of G related to BtB? 10. Find the edge-adjacency matrix of the graph G in Example 3.3, relative to the labelling (e1, . . . , e6). Draw the line graph Λ(G). How many edges has it? 78