Question? Leave a message!

lecture notes on graph theory

graph theory lecture notes mit and graph theory and combinatorics lecture notes | download free pdf
TomTheron Profile Pic
Published Date:09-07-2017
Website URL
GRAPH THEORY Keijo Ruohonen (Translation by Janne Tamminen, Kung-Chung Lee and Robert Piché) 2013Contents 1 I DEFINITIONS AND FUNDAMENTAL CONCEPTS 1 1.1 Definitions 6 1.2 Walks, Trails, Paths, Circuits, Connectivity, Components 10 1.3 Graph Operations 14 1.4 Cuts 18 1.5 Labeled Graphs and Isomorphism 20 II TREES 20 2.1 Trees and Forests 23 2.2 (Fundamental) Circuits and (Fundamental) Cut Sets 27 III DIRECTED GRAPHS 27 3.1 Definition 29 3.2 Directed Trees 32 3.3 Acyclic Directed Graphs 34 IV MATRICES AND VECTOR SPACES OF GRAPHS 34 4.1 Matrix Representation of Graphs 36 4.2 Cut Matrix 40 4.3 Circuit Matrix 43 4.4 An Application: Stationary Linear Networks 48 4.5 Matrices overGF(2) and Vector Spaces of Graphs 50 V GRAPH ALGORITHMS 50 5.1 Computational Complexity of Algorithms 52 5.2 Reachability: Warshall’s Algorithm 53 5.3 Depth-First and Breadth-First Searches 61 5.4 The Lightest Path: Dijkstra’s Algorithm 63 5.5 The Lightest Path: Floyd’s Algorithm 66 5.6 The Lightest Spanning Tree: Kruskal’s and Prim’s Algorithms 71 5.7 The Lightest Hamiltonian Circuit (Travelling Salesman’s Problem): The Annealing Algorithm and the Karp–Held Heuristics 76 5.8 Maximum Matching in Bipartite Graphs: The Hungarian Algorithm 80 5.9 Maximum Flow in a Transport Network: The Ford–Fulkerson Algorithm iii 85 VI DRAWING GRAPHS 85 6.1 Planarity and Planar Embedding 90 6.2 The Davidson–Harel Algorithm 92 VII MATROIDS 92 7.1 Hereditary Systems 93 7.2 The Circuit Matroid of a Graph 96 7.3 Other Basic Matroids 98 7.4 Greedy Algorithm 100 7.5 The General Matroid 102 7.6 Operations on Matroids 106 References 108 Index Foreword These lecture notes were translated from the Finnish lecture notes for the TUT course on graph theory. The laborious bulk translation was taken care of by the students Janne Tamminen (TUT) and Kung-Chung Lee (visiting from the University of British Columbia). Most of the material was then checked by professor Robert Piché. I want to thank the translation team for their effort. The notes form the base text for the course ”MAT-62756 Graph Theory”. They contain an introduction to basic concepts and results in graph theory, with a special emphasis put on the network-theoretic circuit-cut dualism. In many ways a model was the elegant and careful presentation of SWAMY & THULASIRAMAN, especially the older (and better) edition. There are of course many modern text-books with similar contents, e.g. the popular GROSS & YELLEN. One of the usages of graph theory is to give a unified formalism for many very different- looking problems. It then suffices to present algorithms in this common formalism. This has lead to the birth of a special class of algorithms, the so-called graph algorithms. Half of the text of these notes deals with graph algorithms, again putting emphasis on network-theoretic methods. Only basic algorithms, applicable to problems of moderate size, are treated here. Special classes of algorithms, such as those dealing with sparse large graphs, ”small-world” graphs, or parallel algorithms will not be treated. In these algorithms, data structure issues have a large role, too (see e.g. SKIENA). The basis of graph theory is in combinatorics, and the role of ”graphics” is only in visual- izing things. Graph-theoretic applications and models usually involve connections to the ”real world” on the one hand—often expressed in vivid graphical terms—and the definitional and computational methods given by the mathematical combinatoric and linear-algebraic machin- ery on the other. For many, this interplay is what makes graph theory so interesting. There is a part of graph theory which actually deals with graphical drawing and presentation of graphs, briefly touched in Chapter 6, where also simple algorithms are given for planarity testing and drawing. The presentation of the matter is quite superficial, a more profound treatment would require some rather deep results in topology and curve theory. Chapter 7 contains a brief intro- duction to matroids, a nice generalization and substitute for graphs in many ways. Proofs of graph-theoretic results and methods are usually not given in a completely rigorous combinatoric form, but rather using the possibilities of visualization given by graphical presen- tations of graphs. This can lead to situations where the reader may not be completely convinced of the validity of proofs and derivations. One of the goals of a course in graph theory must theniii be to provide the student with the correct ”touch” to such seemingly loose methods of proof. This is indeed necessary, as a completely rigoristic mathematical presentation is often almost unreadable, whereas an excessively slack and lacunar presentation is of course useless. Keijo RuohonenChapter 1 Definitions and Fundamental Concepts 1.1 Definitions Conceptually, a graph is formed by vertices and edges connecting the vertices. Example. Formally, a graph is a pair of sets (V,E), where V is the set of vertices and E is the set of edges, formed by pairs of vertices. E is a multiset, in other words, its elements can occur more than once so that every element has a multiplicity. Often, we label the vertices with letters (for example: a,b,c,... orv ,v ,... ) or numbers1,2,... Throughout this lecture material, we will 1 2 label the elements ofV in this way. Example. (Continuing from the previous example) We label the vertices as follows: v 1 v 5 v v v 2 3 4 We haveV =v ,...,v for the vertices andE =(v ,v ),(v ,v ),(v ,v ),(v ,v ),(v ,v ) 1 5 1 2 2 5 5 5 5 4 5 4 for the edges. Similarly, we often label the edges with letters (for example: a,b,c,... or e ,e ,... ) or num- 1 2 bers1,2,... for simplicity. 1CHAPTER 1. DEFINITIONS AND FUNDAMENTAL CONCEPTS 2 Remark. The two edges(u,v) and(v,u) are the same. In other words, the pair is not ordered. Example. (Continuing from the previous example) We label the edges as follows: v 1 e 3 e v 1 5 e 2 e e 4 5 v v 2 v 4 3 SoE =e ,...,e. 1 5 We have the following terminologies: 1. The two verticesu andv are end vertices of the edge(u,v). 2. Edges that have the same end vertices are parallel. 3. An edge of the form (v,v) is a loop. 4. A graph is simple if it has no parallel edges or loops. 5. A graph with no edges (i.e.E is empty) is empty. 6. A graph with no vertices (i.e.V andE are empty) is a null graph. 7. A graph with only one vertex is trivial. 8. Edges are adjacent if they share a common end vertex. 9. Two verticesu andv are adjacent if they are connected by an edge, in other words,(u,v) is an edge. 10. The degree of the vertexv, written asd(v), is the number of edges withv as an end vertex. By convention, we count a loop twice and parallel edges contribute separately. 11. A pendant vertex is a vertex whose degree is1. 12. An edge that has a pendant vertex as an end vertex is a pendant edge. 13. An isolated vertex is a vertex whose degree is0. Example. (Continuing from the previous example) • v andv are end vertices ofe . 4 5 5 • e ande are parallel. 4 5 • e is a loop. 3 • The graph is not simple. • e ande are adjacent. 1 2CHAPTER 1. DEFINITIONS AND FUNDAMENTAL CONCEPTS 3 • v andv are adjacent. 1 2 • The degree ofv is1 so it is a pendant vertex. 1 • e is a pendant edge. 1 • The degree ofv is5. 5 • The degree ofv is2. 4 • The degree ofv is0 so it is an isolated vertex. 3 In the future, we will label graphs with letters, for example: G = (V,E). The minimum degree of the vertices in a graphG is denotedδ(G) (= 0 if there is an isolated vertex inG). Similarly, we writeΔ(G) as the maximum degree of vertices inG. Example. (Continuing from the previous example)δ(G) = 0 andΔ(G) = 5. Remark. In this course, we only consider finite graphs, i.e.V andE are finite sets. Since every edge has two end vertices, we get Theorem 1.1. The graphG = (V,E), whereV =v ,...,v andE =e ,...,e , satisfies 1 n 1 m n X d(v ) = 2m. i i=1 Corollary. Every graph has an even number of vertices of odd degree. Proof. If the vertices v ,...,v have odd degrees and the vertices v ,...,v have even de- 1 k k+1 n grees, then (Theorem 1.1) d(v )+···+d(v ) = 2m−d(v )−···−d(v ) 1 k k+1 n is even. Therefore,k is even. Example. (Continuing from the previous example) Now the sum of the degrees is 1+2+0+ 2+5 = 10 = 2·5. There are two vertices of odd degree, namelyv andv . 1 5 A simple graph that contains every possible edge between all the vertices is called a complete graph. A complete graph withn vertices is denoted asK . The first four complete graphs are n given as examples: K K 3 4 K K 1 2 The graphG = (V ,E ) is a subgraph ofG = (V ,E ) if 1 1 1 2 2 2 1. V ⊆V and 1 2 2. Every edge ofG is also an edge ofG . 1 2CHAPTER 1. DEFINITIONS AND FUNDAMENTAL CONCEPTS 4 Example. We have the graph v 2 e v 1 4 G : e e 2 2 4 e 5 e v 3 1 v 3 v 5 e 6 and some of its subgraphs are v 2 e 1 G : 1 v 1 v 2 e v 1 4 G : e e 1 2 4 e 5 v 1 v 3 v 5 e 6 v 2 G : 1 e 5 v 1 v 3 v 5 e 6CHAPTER 1. DEFINITIONS AND FUNDAMENTAL CONCEPTS 5 and v 5 G : 1 e 6 The subgraph ofG = (V,E) induced by the edge setE ⊆E is: 1 G = (V ,E ) = hEi, 1 1 1 def. 1 whereV consists of every end vertex of the edges inE . 1 1 Example. (Continuing from above) From the original graphG, the edgese ,e ande induce 2 3 5 the subgraph v 2 〈e ,e ,e 〉: e 2 3 5 2 e 5 v e 1 3 v 3 v 5 The subgraph ofG = (V,E) induced by the vertex setV ⊆V is: 1 G = (V ,E ) = hVi, 1 1 1 def. 1 whereE consists of every edge between the vertices inV . 1 1 Example. (Continuing from the previous example) From the original graphG, the verticesv , 1 v andv induce the subgraph 3 5 〈v ,v ,v 〉: 1 3 5 e 5 e v 3 1 v 3 v 5 e 6 A complete subgraph ofG is called a clique ofG.CHAPTER 1. DEFINITIONS AND FUNDAMENTAL CONCEPTS 6 1.2 Walks, Trails, Paths, Circuits, Connectivity, Components Remark. There are many different variations of the following terminologies. We will adhere to the definitions given here. A walk in the graphG = (V,E) is a finite sequence of the form v ,e ,v ,e ,...,e ,v , i j i j j i 0 1 1 2 k k which consists of alternating vertices and edges ofG. The walk starts at a vertex. Verticesv i t−1 and v are end vertices of e (t = 1,...,k). v is the initial vertex and v is the terminal i j i i t t 0 k vertex. k is the length of the walk. A zero length walk is just a single vertexv . It is allowed to i 0 visit a vertex or go through an edge more than once. A walk is open ifv =6 v . Otherwise it i i 0 k is closed. Example. In the graph v 2 e e 2 1 v 3 v G: 1 e e 8 7 e e e 3 5 10 e 9 v e 5 v 6 4 e 4 v 6 the walk v ,e ,v ,e ,v ,e ,v ,e ,v ,e ,v ,e ,v 2 7 5 8 1 8 5 6 4 5 4 5 4 is open. On the other hand, the walk v ,e ,v ,e ,v ,e ,v ,e ,v ,e ,v 4 5 4 3 3 2 2 7 5 6 4 is closed. A walk is a trail if any edge is traversed at most once. Then, the number of times that the vertex pair u,v can appear as consecutive vertices in a trail is at most the number of parallel edges connectingu andv. Example. (Continuing from the previous example) The walk in the graph v ,e ,v ,e ,v ,e ,v ,e ,v ,e ,v ,e ,v ,e ,v 1 8 5 9 1 1 2 7 5 6 4 5 4 4 4 is a trail. A trail is a path if any vertex is visited at most once except possibly the initial and terminal vertices when they are the same. A closed path is a circuit. For simplicity, we will assume in the future that a circuit is not empty, i.e. its length≥ 1. We identify the paths and circuits with the subgraphs induced by their edges.CHAPTER 1. DEFINITIONS AND FUNDAMENTAL CONCEPTS 7 Example. (Continuing from the previous example) The walk v ,e ,v ,e ,v ,e ,v 2 7 5 6 4 3 3 is a path and the walk v ,e ,v ,e ,v ,e ,v ,e ,v 2 7 5 6 4 3 3 2 2 is a circuit. The walk starting atu and ending atv is called anu–v walk. u andv are connected if there is au–v walk in the graph (then there is also au–v path). Ifu andv are connected andv andw are connected, thenu andw are also connected, i.e. if there is au–v walk and av–w walk, then there is also a u–w walk. A graph is connected if all the vertices are connected to each other. (A trivial graph is connected by convention.) Example. The graph is not connected. The subgraphG (not a null graph) of the graphG is a component ofG if 1 1. G is connected and 1 2. Either G is trivial (one single isolated vertex of G) or G is not trivial and G is the 1 1 1 subgraph induced by those edges ofG that have one end vertex inG . 1 Different components of the same graph do not have any common vertices because of the fol- lowing theorem. Theorem 1.2. If the graphG has a vertexv that is connected to a vertex of the componentG 1 ofG, thenv is also a vertex ofG . 1 ′ Proof. Ifv is connected to vertexv ofG , then there is a walk inG 1 ′ v =v ,e ,v ,...,v ,e ,v =v. i j i i j i 0 1 1 k−1 k k ′ Since v is a vertex of G , then (condition 2 above) e is an edge of G and v is a vertex 1 j 1 i k k−1 ofG . We continue this process and see thatv is a vertex ofG . 1 1 Example. e 5 G: v 3 v 6 e e 4 v 1 e v 7 3 4 e v 2 1 e 6 e 7 v v 5 2 v 8 G G G G 1 2 3 4 The components ofG areG ,G ,G andG . 1 2 3 4CHAPTER 1. DEFINITIONS AND FUNDAMENTAL CONCEPTS 8 Theorem 1.3. Every vertex ofG belongs to exactly one component ofG. Similarly, every edge ofG belongs to exactly one component ofG. Proof. We choose a vertexv inG. We do the following as many times as possible starting with V =v: 1 ′ ′ ′ (∗) If v is a vertex of G such that v ∈/ V and v is connected to some vertex of V , then 1 1 ′ V ←V ∪v. 1 1 Since there is a finite number of vertices inG, the process stops eventually. The lastV induces a 1 subgraphG ofG that is the component ofG containingv. G is connected because its vertices 1 1 are connected tov so they are also connected to each other. Condition 2 holds because we can not repeat (∗). By Theorem 1.2,v does not belong to any other component. The edges of the graph are incident to the end vertices of the components. Theorem 1.3 divides a graph into distinct components. The proof of the theorem gives an algorithm to do that. We have to repeat what we did in the proof as long as we have free vertices that do not belong to any component. Every isolated vertex forms its own component. A connected graph has only one component, namely, itself. A graphG withn vertices,m edges andk components has the rank ρ(G) =n−k. The nullity of the graph is μ(G) = m−n+k. We see thatρ(G)≥ 0 andρ(G)+μ(G) =m. In addition,μ(G)≥ 0 because Theorem 1.4. ρ(G)≤m Proof. We will use the second principle of induction (strong induction) form. Induction Basis: m = 0. The components are trivial andn =k. Induction Hypothesis: The theorem is true form p. (p≥ 1) Induction Statement: The theorem is true form =p. Induction Statement Proof: We choose a component G of G which has at least one edge. 1 We label that edgee and the end vertices u and v. We also label G as the subgraph of G and 2 ′ G , obtained by removing the edgee fromG (but not the verticesu andv). We labelG as the 1 1 ′ graph obtained by removing the edgee from G (but not the vertices u and v) and let k be the ′ number of components ofG . We have two cases: ′ ′ 1. G is connected. Then,k =k. We use the Induction Hypothesis onG : 2 ′ ′ n−k = n−k =ρ(G)≤ m−1 m. 2. G is not connected. Then there is only one path betweenu andv: 2 u,e,v ′ and no other path. Thus, there are two components in G and k = k + 1. We use the 2 ′ Induction Hypothesis onG : ′ ′ ρ(G) = n−k = n−k−1≤m−1.CHAPTER 1. DEFINITIONS AND FUNDAMENTAL CONCEPTS 9 Hencen−k≤m. These kind of combinatorial results have many consequences. For example: Theorem 1.5. IfG is a connected graph andk≥ 2 is the maximum path length, then any two paths inG with lengthk share at least one common vertex. Proof. We only consider the case where the paths are not circuits (Other cases can be proven in a similar way.). Consider two paths ofG with lengthk: v ,e ,v ,e ,...,e ,v (pathp ) i j i j j i 1 0 1 1 2 k k and ′ ′ ′ ′ ′ ′ v ,e ,v ,e ,...,e ,v (pathp ). i j i j j i 2 0 1 1 2 k k Let us consider the counter hypothesis: The paths p and p do not share a common vertex. 1 2 ′ Since G is connected, there exists an v –v path. We then find the last vertex on this path i i 0 k which is also onp (at leastv is onp ) and we label that vertexv . We find the first vertex of 1 i 1 i 0 t ′ ′ ′ thev –v path which is also onp (at leastv is onp ) and we label that vertexv . So we get i i 2 i 2 i t s k k av –v ′ path i i t s ′′ ′′ ′ v ,e ,...,e ,v . i i t j j s 1 ℓ The situation is as follows: v ,e ,v ,...,v ,e ,...,e ,v i j i i j j i 0 1 1 t t+1 k k ′′ e j 1 . . . ′′ e j ℓ ′ ′ ′ ′ ′ ′ ′ v ,e ,v ,...,v ,e ,...,e ,v i j i i j j i s 0 1 1 s+1 k k ′ ′ From here we get two paths: v –v path andv –v path. The two cases are: i i 0 i i k k 0 √ 1 ′ • t≥s: Now the length of thev –v path is≥k+1. i i 0 k √ ′ • t s: Now the length of thev –v path is≥k+1. i i k 0 A graph is circuitless if it does not have any circuit in it. Theorem 1.6. A graph is circuitless exactly when there are no loops and there is at most one path between any two given vertices. Proof. First let us assume G is circuitless. Then, there are no loops in G. Let us assume the counter hypothesis: There are two different paths between distinct verticesu andv inG: u = v ,e ,v ,e ,...,e ,v = v (pathp ) i j i j j i 1 0 1 1 2 k k and ′ ′ ′ ′ ′ ′ u =v ,e ,v ,e ,...,e ,v = v (pathp ) i j i j j i 2 0 1 1 2 ℓ ℓ ′ ′ (here we havei =i andi = i ), wherek≥ℓ. We choose the smallest indext such that 0 k 0 ℓ v =6 v ′. i i t t There is such at because otherwise √ 1 From now on, the symbol means contradiction. If we get a contradiction by proceeding from the assump- tions, the hypothesis must be wrong.CHAPTER 1. DEFINITIONS AND FUNDAMENTAL CONCEPTS 10 √ ′ 1. k ℓ andv =v =v = v ( ) or i i i k ℓ ℓ 2. k = ℓ andv = v ′,...,v = v ′ . Then, there would be two parallel edges between two i i i i 0 ℓ 0 ℓ consecutive vertices in the path. That would imply the existence of a circuit between two √ vertices inG. p 1 v u v v i i s t–1 p 2 We choose the smallest indexs such thats≥ t andv is in the pathp (at leastv is inp ). We i 2 i 2 s k ′ choose an indexr such thatr≥t andv =v (it exists becausep is a path). Then, i i 1 s r ′ ′ ′ ′ v ,e ,...,e ,v (= v ),e ,...,e ,v (= v ) i j j i i j j i i t−1 t s s t−1 r r t t−1 √ is a circuit. (Verify the caset = s = r.) Let us prove the reverse implication. If the graph does not have any loops and no two distinct vertices have two different paths between them, then there is no circuit. For example, if v ,e ,v ,e ,...,e ,v =v i j i j j i i 0 1 1 2 k k 0 √ is a circuit, then either k = 1 and e is a loop ( ), or k≥ 2 and the two vertices v and v j i i 1 0 1 are connected by two distinct paths √ v ,e ,v and v ,e ,...,e ,v = v ( ). i j i i j j i i 0 1 1 1 2 k k 0 1.3 Graph Operations The complement of the simple graph G = (V,E) is the simple graph G = (V,E), where the edges inE are exactly the edges not inG. Example. v v 3 2 G: v 5 v v 1 4 v 3 v 2 _ G: v 5 v v 1 4CHAPTER 1. DEFINITIONS AND FUNDAMENTAL CONCEPTS 11 Example. The complement of the complete graphK is the empty graph withn vertices. n ′ ′ ′ ′ Obviously,G = G. If the graphsG = (V,E) andG = (V ,E ) are simple andV ⊆ V , then ′ ′′ ′′ the difference graph is G−G = (V,E ), whereE contains those edges from G that are not ′ inG (simple graph). Example. G: G': G – G': Here are some binary operations between two simple graphs G = (V ,E ) and G = 1 1 1 2 (V ,E ): 2 2 • The union isG ∪G = (V ∪V ,E ∪E ) (simple graph). 1 2 1 2 1 2 • The intersection isG ∩G = (V ∩V ,E ∩E ) (simple graph). 1 2 1 2 1 2 • The ring sumG⊕G is the subgraph ofG∪G induced by the edge setE⊕E (simple 1 2 1 2 1 2 graph). Note The set operation⊕ is the symmetric difference, i.e. E ⊕E = (E −E )∪(E −E ). 1 2 1 2 2 1 Since the ring sum is a subgraph induced by an edge set, there are no isolated vertices. All three operations are commutative and associative. Example. For the graphs v v v 2 1 1 e 2 v 5 e 3 e e G : G : e 1 5 1 2 1 e 6 v 7 v v v 3 4 3 e 4 e 7 v 6CHAPTER 1. DEFINITIONS AND FUNDAMENTAL CONCEPTS 12 we have v v 2 1 e 2 v 5 e 3 e e G ∪ G : 1 2 5 1 e 6 v 7 v v 3 4 e 4 e 7 v 6 v 1 v v 1 2 e 2 e e G ∩ G : 3 1 1 2 e G ⊕ G : 1 2 5 e e 6 v 4 3 v v 3 4 e 7 v 6 Remark. The operations∪,∩ and⊕ can also be defined for more general graphs other than simple graphs. Naturally, we have to ”keep track” of the multiplicity of the edges: ∪ : The multiplicity of an edge inG ∪G is the larger of its multiplicities inG andG . 1 2 1 2 ∩ : The multiplicity of an edge inG ∩G is the smaller of its multiplicities inG andG . 1 2 1 2 ⊕ : The multiplicity of an edge in G ⊕G ism −m, where m is its multiplicity in G 1 2 1 2 1 1 andm is its multiplicity inG . 2 2 (We assume zero multiplicity for the absence of an edge.) In addition, we can generalize the dif- ference operation for all kinds of graphs if we take account of the multiplicity. The multiplicity ′ of the edgee in the differenceG−G is ( m −m , ifm ≥m 1 2 1 2 ˙ m −m = (also known as the proper difference), 1 2 0, ifm m 1 2 wherem andm are the multiplicities ofe inG andG , respectively. 1 2 1 2 If v is a vertex of the graph G = (V,E), then G−v is the subgraph of G induced by the vertex setV−v. We call this operation the removal of a vertex. Example. (Continuing from the previous example) v v 2 1 v 5 e 3 e G – v : 1 1 4 v 3CHAPTER 1. DEFINITIONS AND FUNDAMENTAL CONCEPTS 13 ′ ′ Similarly, if e is an edge of the graph G = (V,E), then G−e is graph (V,E ), where E is obtained by removing e from E. This operation is known as removal of an edge. We remark that we are not talking about removing an edge as in Set Theory, because the edge can have nonunit multiplicity and we only remove the edge once. Example. (Continuing from the previous example) v v 1 2 e 2 v 5 e 3 e G – e : 1 1 5 v v 3 4 e 4 If u and v are two distinct vertices of the graph G = (V,E), then we can short-circuit the ′ ′ two verticesu andv and obtain the graph(V ,E ), where ′ V = (V−u,v)∪w (w∈/ V is the ”new” vertex) and ′ ′ ′ ′ ′ ′ ′ E = (E−(v,u),(v,v)v ∈V)∪(v,w) (v,u)∈E or(v,v)∈E ∪(w,w) (u,u)∈E or(v,v)∈E (Recall that the pair of vertices corresponding to an edge is not ordered). Note We have to maintain the multiplicity of the edges. In particular, the edge(u,v) becomes a loop. Example. (Continuing from the previous example) Short-circuitv andv in the graphG : 3 4 1 v v 1 2 v 5 w In the graph G = (V,E), contracting the edge e = (u,v) (not a loop) means the operation in which we first removee and then short-circuitu andv. (Contracting a loop simply removes that loop.) Example. (Continuing from the previous example) We contract the edge e in G by first re- 3 1 movinge and then short-circuitingv andv . 3 2 3CHAPTER 1. DEFINITIONS AND FUNDAMENTAL CONCEPTS 14 v v 1 2 e 2 v 5 e e 1 5 v v 3 4 e 4 v 1 e 2 v 5 w v 4 Remark. If we restrict short-circuiting and contracting to simple graphs, then we remove loops and all but one of the parallel edges between end vertices from the results. 1.4 Cuts A vertexv of a graphG is a cut vertex or an articulation vertex ofG if the graphG−v consists of a greater number of components thanG. Example. v is a cut vertex of the graph below: cut vertex v G: G – v: (Note Generally, the only vertex of a trivial graph is not a cut vertex, neither is an isolated vertex.) A graph is separable if it is not connected or if there exists at least one cut vertex in the graph. Otherwise, the graph is nonseparable. Example. The graphG in the previous example is separable. Example. The graph below is nonseparable.CHAPTER 1. DEFINITIONS AND FUNDAMENTAL CONCEPTS 15 A block of the graphG is a subgraphG ofG (not a null graph) such that 1 • G is nonseparable, and 1 • ifG is any other subgraph ofG, thenG ∪G = G orG ∪G is separable (think about 2 1 2 1 1 2 that). Example. The graph below is separable: cut vertex Theorem 1.7. The vertex v is a cut vertex of the connected graph G if and only if there exist two verticesu andw in the graphG such that (i) v =6 u,v =6 w andu =6 w, but (ii) v is on everyu–w path. Proof. First, let us consider the case thatv is a cut-vertex of G. Then, G−v is not connected and there are at least two components G = (V ,E ) and G = (V ,E ). We choose u∈ V 1 1 1 2 2 2 1 andw∈V . Theu–w path is inG because it is connected. Ifv is not on this path, then the path 2 √ is also inG−v ( ). The same reasoning can be used for all theu–w paths inG. Ifv is in everyu–w path, then the verticesu andw are not connected inG−v.CHAPTER 1. DEFINITIONS AND FUNDAMENTAL CONCEPTS 16 Theorem 1.8. A nontrivial simple graph has at least two vertices which are not cut vertices. Proof. We will use induction for the graphG withn vertices. Induction Basis: The casen = 2 is obviously true. Induction Hypothesis: The theorem is true forn≤ k. (k≥ 2) Induction Statement: The theorem is true forn =k+1. Induction Statement Proof: If there are no cut vertices in G, then it is obvious. Otherwise, we consider a cut vertex v of G. Let G ,...,G be the components of G−v (so m≥ 2). 1 m Every componentG falls into one of the two cases: i 1. G is trivial so the only vertex ofG is a pendant vertex or an isolated vertex ofG but it is i i not a cut vertex ofG. 2. G is not trivial. The Induction Hypothesis tells us that there exist two vertices u and w i inG which are not cut vertices ofG . Ifv andu (respectivelyv andw) are not adjacent i i inG, thenu (respectivelyw) is not a cut vertex inG. If bothv andu as well asu andw are adjacent inG, thenu andw can not be cut vertices ofG. A cut set of the connected graphG = (V,E) is an edge setF⊆E such that 1. G−F (remove the edges ofF one by one) is not connected, and 2. G−H is connected wheneverH⊂F . Theorem 1.9. IfF is a cut set of the connected graphG, thenG−F has two components. Proof. LetF =e ,...,e. The graphG−e ,...,e is connected (and so isG ifk = 1) 1 k 1 k−1 by condition 2. When we remove the edges from the connected graph, we get at most two components. Example. In the graph e v 8 6 v e 4 v 2 2 e e e e 1 3 5 7 v v 5 1 e e v 6 4 3 e ,e,e ,e,e ,e ,e,e,e ,e ,e ,e,e ,e ,e,e ,e ,e ande ,e ,e are 1 4 6 7 1 2 3 8 3 4 5 6 2 5 7 2 5 6 2 3 4 cut sets. Are there other cut sets? In a graphG = (V,E), a pair of subsetsV andV ofV satisfying 1 2 V =V ∪V , V ∩V =∅ , V 6=∅, V 6=∅, 1 2 1 2 1 2 is called a cut (or a partition) ofG, denotedhV ,Vi. Usually, the cutshV ,Vi andhV ,Vi are 1 2 1 2 2 1 considered to be the same.