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
TomTheron,Japan,Teacher
Published Date:09-07-2017
Your Website URL(Optional)
Comment
GRAPH THEORY Keijo Ruohonen (Translation by Janne Tamminen, Kung-Chung Lee and Robert Piché) 2013Chapter 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.CHAPTER 1. DEFINITIONS AND FUNDAMENTAL CONCEPTS 17 Example. (Continuing from the previous example)hv ,v ,v,v ,v ,vi is a cut. 1 2 3 4 5 6 We can also think of a cut as an edge set: cuthV ,Vi =those edges with one end vertex inV and the other end vertex inV. 1 2 1 2 (Note This edge set does not defineV andV uniquely so we can not use this for the definition 1 2 of a cut.) Using the previous definitions and concepts, we can easily prove the following: 1. The cuthV ,Vi of a connected graph G (considered as an edge set) is a cut set if and 1 2 only if the subgraphs induced by V and V are connected, i.e. G−hV ,Vi has two 1 2 1 2 components. 2. If F is a cut set of the connected graph G and V and V are the vertex sets of the two 1 2 components ofG−F , thenhV ,Vi is a cut andF =hV ,Vi. 1 2 1 2 3. Ifv is a vertex of a connected (nontrivial) graphG = (V,E), thenhv,V−vi is a cut ofG. It follows that the cut is a cut set if the subgraph (i.e.G−v) induced byV−v is connected, i.e. ifv is not a cut vertex. If there exists a cuthV ,Vi for the graph G = (V,E) so that E =hV ,Vi, i.e. the cut 1 2 1 2 (considered as an edge set) includes every edge, then the graphG is bipartite. Example. The graph v 4 v 1 v 5 v 2 v 6 v 3 v 7 is bipartite. V =v ,v ,v andV =v ,v ,v ,v. 1 1 2 3 2 4 5 6 7 A simple bipartite graph is called a complete bipartite graph if we can not possibly add any more edges to the edge sethV ,Vi, i.e. the graph contains exactly all edges that have one end 1 2 vertex inV and the other end vertex inV . If there aren vertices inV andm vertices inV , we 1 2 1 2 denote it asK (cf. complete graph). n,mCHAPTER 1. DEFINITIONS AND FUNDAMENTAL CONCEPTS 18 Example. K : K : K : 2,1 1,1 1,2 K : 2,3 (UsuallyK andK are considered to be the same.) n,m m,n 1.5 Labeled Graphs and Isomorphism By a labeling of the vertices of the graphG = (V,E), we mean a mappingα : V → A, where A is called the label set. Similarly, a labeling of the edges is a mappingβ :E→ B, whereB is the label set. Often, these labels are numbers. Then, we call them weights of vertices and edges. In a weighted graph, the weight of a path is the sum of the weights of the edges traversed. The labeling of the vertices (respectively edges) is injective if distinct vertices (respectively edges) have distinct labels. An injective labeling is bijective if there are as many labels in A (respectively inB) as the number of vertices (respectively edges). Example. IfA =0,1 andB =R, then in the graph, 1 0.1 1 0.2 0 0.4 0.7 0.6 0 0 1 the labeling of the edges (weights) is injective but not the labeling of the vertices. The two graphsG = (V ,E ) andG = (V ,E ) are isomorphic if labeling the vertices of 1 1 1 2 2 2 G bijectively with the elements ofV givesG . (Note We have to maintain the multiplicity of 1 2 2 the edges.)CHAPTER 1. DEFINITIONS AND FUNDAMENTAL CONCEPTS 19 ′ Example. The graphs G and G are isomorphic and the vertex labeling v 7→ v and edge 1 2 i i ′ labelinge 7→e define the isomorphism. j j v 6 v 5 e v 2 e 1 7 e 10 e 3 e e 8 G : 6 1 e 1 v e v 3 5 e 8 9 v v 2 4 e 4 v 7 e' 9 v' e' 7 2 G : 2 v' v' v' v' e' 6 5 4 2 10 v' v' 1 8 e' e' e' e' 7 5 4 1 e' 3 e' 8 v' e' 6 3 2 Determining whether or not two graphs are isomorphic is a well researched problem. It differs significantly from other problems in graph theory and network analysis. In addition, it has a lot to do with group theory in algebra. The problem is important in the theory of Computational Complexity. For example, refer to KÖBLER, J. & SCHÖNING, U. & TORÁN, J.: The Graph Isomorphism Problem. Its Structural Complexity. Birkhäuser (1993). 2 Maybe too well, cf. READ, R.C. & CORNEIL, D.G.: The Graph Isomorphism Disease. Journal of Graph Theory 1 (1977), 339–363.