Ch.10: Graphs and Trees
Chapter 10 of the book "Discrete Mathematics with Applications" by Susanna S. Epp (4th edition) 10.1. Graphs: Definitions and Basic Properties 10.2. Trails, Paths, and Circuits 10.3. Matrix Representations of Graphs 10.4. Isomorphisms of Graphs 10.5. Trees 10.6. Rooted Trees 10.7. Spanning Trees and Shortest Paths
233 flashcards · Mathematics · by lakesare
Part of Textbooks › Discrete Mathematics with Applications (Susanna Epp) · 12 courses
[Graphs: Definitions and Basic Properties] What is a graph GGG ?
Two finite sets: a nonempty set V(G)V(G)V(G) of vertices and a set E(G)E(G)E(G) of edges, where each edge is associated with a set of one or two vertices, called its endpoints. Example: V(G)={v1,v2}V(G) = \{v_1, v_2\}V(G)={v1,v2} , E(G)={e1,e2}E(G) = \{e_1, e_2\}E(G)={e1,e2} , where e1e_1e1 has endpoints {v1,v2}\{v_1, v_2\}{v1,v2} and e2e_2e2 has the single endpoint v1v_1v1 .
[Graphs: Definitions and Basic Properties] In a graph, what is the edge-endpoint function?
The correspondence that assigns to each edge its set of endpoints. It is usually given as a table with the columns "Edge" and "Endpoints".Example: e1↦{v1,v2}e_1 \mapsto \{v_1, v_2\}e1↦{v1,v2} , e2↦{v1}\ e_2 \mapsto \{v_1\} e2↦{v1} .
[Graphs: Definitions and Basic Properties] In a graph, what is a loop, and when are two edges parallel?
Loop: an edge with just one endpoint. Parallel: two or more distinct edges with the same set of endpoints. Example: e5e_5e5 is a loop at v4v_4v4 ; e2e_2e2 and e3e_3e3 are parallel (both have endpoints {v2,v3}\{v_2, v_3\}{v2,v3} ).
[Graphs: Definitions and Basic Properties] In a graph, when is an edge incident on a vertex?
When the vertex is one of the edge's endpoints. An edge also connects its endpoints.Example: an edge eee with endpoints {v,w}\{v, w\}{v,w} is incident on vvv and on www .
[Graphs: Definitions and Basic Properties] In a graph, when are two vertices adjacent, and when is a vertex adjacent to itself?
Two vertices are adjacent when an edge connects them; a vertex is adjacent to itself when it is an endpoint of a loop. Example: an edge with endpoints {v,w}\{v, w\}{v,w} makes vvv and www adjacent; a loop with endpoint {u}\{u\}{u} makes uuu adjacent to itself.
[Graphs: Definitions and Basic Properties] In a graph, when are two edges adjacent?
When they are incident on the same endpoint. Example: edges with endpoints {v1,v2}\{v_1, v_2\}{v1,v2} and {v2,v3}\{v_2, v_3\}{v2,v3} are adjacent (both are incident on v2v_2v2 ).
[Graphs: Definitions and Basic Properties] A vertex on which no edges are incident is called isolated.
Example: in the graph with V={v1,v2,v3}V = \{v_1, v_2, v_3\}V={v1,v2,v3} and one edge with endpoints {v1,v2}\{v_1, v_2\}{v1,v2} , the vertex v3v_3v3 is isolated.
[Graphs: Definitions and Basic Properties] Write the vertex set, the edge set and the table of the edge-endpoint function of this graph.
Vertex set {v1,…,v6}\{v_1, \dots, v_6\}{v1,…,v6} , edge set {e1,…,e7}\{e_1, \dots, e_7\}{e1,…,e7} , edge-endpoint function: EdgeEndpointse1{v1,v2}e2{v1,v3}e3{v1,v3}e4{v2,v3}e5{v5,v6}e6{v5}e7{v6}\begin{array}{c|c} \text{Edge} & \text{Endpoints} \\ \hline e_1 & \{v_1, v_2\} \\ e_2 & \{v_1, v_3\} \\ e_3 & \{v_1, v_3\} \\ e_4 & \{v_2, v_3\} \\ e_5 & \{v_5, v_6\} \\ e_6 & \{v_5\} \\ e_7 & \{v_6\} \end{array}Edgee1e2e3e4e5e6e7Endpoints{v1,v2}{v1,v3}{v1,v3}{v2,v3}{v5,v6}{v5}{v6…
[Graphs: Definitions and Basic Properties] Must every vertex of a graph be an endpoint of some edge?
No. Every edge must have one or two endpoints, but a vertex need not be an endpoint of any edge (such a vertex is isolated).Example: V={v1,v2}V = \{v_1, v_2\}V={v1,v2} and E=∅E = \varnothingE=∅ is a graph.
[Graphs: Definitions and Basic Properties] In this graph, find the edges incident on v1v_1v1 , the vertices adjacent to v1v_1v1 , the edges adjacent to e1e_1e1 , the loops, the parallel edges, the vertices adjacent to themselves, and the isolated vertices.
Edges incident on v1v_1v1 e1,e2,e3e_1, e_2, e_3e1,e2,e3 Vertices adjacent to v1v_1v1 v2,v3v_2, v_3v2,v3 Edges adjacent to e1e_1e1 e2,e3,e4e_2, e_3, e_4e2,e3,e4 Loops e6,e7e_6, e_7e6,e7 Parallel edges e2e_2e2 and e3e_3e3 Vertices adjacent to themselves v5,v6v_5, v_6v5,v6 Isolated vertices v4v_4v4
[Graphs: Definitions and Basic Properties] How are a graph and its drawings (pictorial representations) related?
A drawing determines the graph uniquely, but one graph can have many different drawings. Lengths and curvatures of the edges and positions of the vertices may vary from drawing to drawing. Example: (a) and (b) both show the graph with e1↦{v1,v3}e_1 \mapsto \{v_1, v_3\}e1↦{v1,v3} , e2↦{v2,v4}e_2 \mapsto \{v_2, v_4\}e2↦{v2,v4} , e3↦{v2,v4}e_3 \mapsto \{v_2, v_4\}e3↦{v2,v4} , e4↦{v3}e_4 \mapsto \{v_3\}e4↦{v3} .
[Graphs: Definitions and Basic Properties] Label the vertices and edges of both drawings so that they represent the same graph.
Follow the edges of the star in order, labeling the vertices v1,…,v5v_1, \dots, v_5v1,…,v5 and the edges e1,…,e5e_1, \dots, e_5e1,…,e5 ; label the pentagon in the same cyclic order. Both have edge-endpoint function e1↦{v1,v2}e_1 \mapsto \{v_1, v_2\}e1↦{v1,v2} , e2↦{v2,v3}e_2 \mapsto \{v_2, v_3\}e2↦{v2,v3} , e3↦{v3,v4}e_3 \mapsto \{v_3, v_4\}e3↦{v3,v4} , e4↦{v4,v5}e_4 \mapsto \{v_4, v_5\}e4↦{v4,v5} , e5↦{v5,v1}e_5 \mapsto \{v_5, v_1\}e5↦{v5,v1} .
[Graphs: Definitions and Basic Properties] What is a directed graph (digraph)?
A nonempty finite set V(G)V(G)V(G) of vertices and a finite set D(G)D(G)D(G) of directed edges, each associated with an ordered pair of vertices (its endpoints). An edge associated with (v,w)(v, w)(v,w) is the directed edge from vvv to www , drawn as an arrow from vvv to www .Example: V={v1,v2}V = \{v_1, v_2\}V={v1,v2} , D={e}D = \{e\}D={e} with e↦(v1,v2)e \mapsto (v_1, v_2)e↦(v1,v2) : one arrow from v1v_1v1 to v2v_2v2 .
[Graphs: Definitions and Basic Properties] Which ordinary (undirected) graph is associated with a directed graph?
The graph obtained by ignoring the directions of the edges. Example: directed edges (v1,v2)(v_1, v_2)(v1,v2) and (v2,v1)(v_2, v_1)(v2,v1) become two parallel edges with endpoints {v1,v2}\{v_1, v_2\}{v1,v2} .
[Graphs: Definitions and Basic Properties] According to this knowledge base, what paper finish does the New York Times use?
Matte. New York Times undefinedinstance-of\xrightarrow{\text{instance-of}}instance-of big-city daily undefinedis-a\xrightarrow{\text{is-a}}is-a newspaper undefinedpaper-finish\xrightarrow{\text{paper-finish}}paper-finish matte.
[Graphs: Definitions and Basic Properties] Two vegetarians and two cannibals are on the left bank of a river with a boat that holds at most two people. All must cross to the right bank, and on no bank with vegetarians may the cannibals outnumber the vegetarians.How does the book turn this puzzle into a graph?
Vertices: the reachable arrangements of people and boat; an edge joins two arrangements when one legal move leads from one to the other. Notation: (vvc/Bc)(vvc/Bc)(vvc/Bc) means two vegetarians and one cannibal on the left bank, one cannibal and the boat on the right bank.The edges are undirected because every legal move can be reversed.
[Graphs: Definitions and Basic Properties] Vegetarians and cannibals: two vegetarians ( vvv ) and two cannibals ( ccc ) must cross a river in a boat ( BBB ) holding at most two; on no bank with vegetarians may the cannibals outnumber them. (vvc/Bc)(vvc/Bc)(vvc/Bc) means vvcvvcvvc on the left bank, ccc and the boat on the right.Give a sequence of moves from (vvccB/)(vvccB/)(vvccB/) to (/Bvvcc)(/Bvvcc)(/Bvvcc) .
(vvccB/)→(vc/Bvc)→(vvcB/c)→(c/Bvvc)→(ccB/vv)→(/Bvvcc)\boldsymbol{(vvccB/) \to (vc/Bvc) \to (vvcB/c) \to (c/Bvvc) \to (ccB/vv) \to (/Bvvcc)}(vvccB/)→(vc/Bvc)→(vvcB/c)→(c/Bvvc)→(ccB/vv)→(/Bvvcc) The graph of all reachable arrangements; each edge is one legal move.
[Graphs: Definitions and Basic Properties] What is a simple graph?
A graph with no loops and no parallel edges. So two endpoints determine an edge, and the edge with endpoints vvv and www is written {v,w}\{v, w\}{v,w} .Example: V={u,v,w}V = \{u, v, w\}V={u,v,w} , E={{u,v},{v,w}}E = \{\{u, v\}, \{v, w\}\}E={{u,v},{v,w}} .
[Graphs: Definitions and Basic Properties] How many simple graphs have the vertex set {u,v,w,x}\{u, v, w, x\}{u,v,w,x} and exactly two edges, one of which is {u,v}\{u, v\}{u,v} ?
5 There are (42)=6\binom{4}{2} = 6(24)=6 possible edges (2-element subsets of the vertices); the second edge is any of the 5 others.
[Graphs: Definitions and Basic Properties] What is the complete graph on nnn vertices, KnK_nKn ( nnn a positive integer)?
The simple graph with nnn vertices and exactly one edge connecting each pair of distinct vertices. The KKK stands for the German word "komplett" (complete).
[Graphs: Definitions and Basic Properties] What is the complete bipartite graph on (m,n)(m, n)(m,n) vertices, Km,nK_{m,n}Km,n ( m,nm, nm,n positive integers)?
The simple graph with vertices v1,…,vmv_1, \dots, v_mv1,…,vm and w1,…,wnw_1, \dots, w_nw1,…,wn , with an edge from each viv_ivi to each wjw_jwj , and no edge between two vvv 's or between two www 's. Example: K3,2K_{3,2}K3,2 has 3⋅2=63 \cdot 2 = 63⋅2=6 edges, K3,3K_{3,3}K3,3 has 9.
[Graphs: Definitions and Basic Properties] When is a graph HHH a subgraph of a graph GGG ?
Every vertex of HHH is a vertex of GGG , every edge of HHH is an edge of GGG , and every edge of HHH has the same endpoints in HHH as in GGG . Example: the graph with vertex v1v_1v1 and a loop e3e_3e3 at v1v_1v1 is a subgraph of any graph that has the loop e3e_3e3 at v1v_1v1 .
[Graphs: Definitions and Basic Properties] GGG has vertices v1,v2v_1, v_2v1,v2 and edges e1,e2e_1, e_2e1,e2 (both with endpoints {v1,v2}\{v_1, v_2\}{v1,v2} ) and a loop e3e_3e3 at v1v_1v1 . How many subgraphs does GGG have?
11 No edges: {v1}\{v_1\}{v1} , {v2}\{v_2\}{v2} , {v1,v2}\{v_1, v_2\}{v1,v2} : 3. One edge: e1e_1e1 or e2e_2e2 (needs both vertices), e3e_3e3 with or without v2v_2v2 : 4. Two edges: 3. Three edges: 1. Total 3+4+3+1=113 + 4 + 3 + 1 = 113+4+3+1=11 .
[Graphs: Definitions and Basic Properties] What is the degree deg(v)\deg(v)deg(v) of a vertex vvv of a graph?
The number of edges incident on vvv , where a loop is counted twice. So deg(v)\deg(v)deg(v) is the number of end segments of edges at vvv in a drawing. Example: one loop and three other edges: degree 2+3=52 + 3 = 52+3=5 .
[Graphs: Definitions and Basic Properties] What is the total degree of a graph GGG ?
The sum of the degrees of all the vertices of GGG . Example: a graph with one edge {v1,v2}\{v_1, v_2\}{v1,v2} and an isolated vertex v3v_3v3 has total degree 1+1+0=21 + 1 + 0 = 21+1+0=2 .
[Graphs: Definitions and Basic Properties] Find the degree of each vertex and the total degree of this graph.
deg(v1)=0, deg(v2)=2, deg(v3)=4\boldsymbol{\deg(v_1) = 0, \ \deg(v_2) = 2, \ \deg(v_3) = 4}deg(v1)=0, deg(v2)=2, deg(v3)=4 ; total degree 6 e1e_1e1 and e2e_2e2 are incident on v2v_2v2 and v3v_3v3 ; the loop e3e_3e3 contributes 2 to deg(v3)\deg(v_3)deg(v3) . The graph has 3 edges, and 6=2⋅36 = 2 \cdot 36=2⋅3 .
[Graphs: Definitions and Basic Properties] The Handshake Theorem If GGG is any graph with vertices v1,…,vnv_1, \dots, v_nv1,…,vn , then deg(v1)+deg(v2)+⋯+deg(vn)= ?\deg(v_1) + \deg(v_2) + \dots + \deg(v_n) = \; ?deg(v1)+deg(v2)+⋯+deg(vn)=?
2⋅(the number of edges of G)\boldsymbol{2 \cdot (\text{the number of edges of } G)}2⋅(the number of edges of G) Example: a triangle K3K_3K3 has 3 edges and total degree 2+2+2=62 + 2 + 2 = 62+2+2=6 .
[Graphs: Definitions and Basic Properties] Handshake Theorem: the total degree of any graph equals twice its number of edges.Why is it called the handshake theorem?
At a party, each handshake is counted by two people, so the numbers of handshakes of all people add up to twice the number of handshakes. People are vertices, handshakes are edges, and the number of handshakes of a person is the degree.
[Graphs: Definitions and Basic Properties] Handshake Theorem: the total degree of any graph equals twice its number of edges.How is it proved?
Each edge contributes exactly 2 to the total degree: 1 to the degree of each endpoint vi,vjv_i, v_jvi,vj , and 2 to deg(vi)\deg(v_i)deg(vi) if it is a loop ( i=ji = ji=j ). Since every edge contributes 2, the total degree is 2⋅2 \cdot2⋅ (number of edges).
[Graphs: Definitions and Basic Properties] Corollary 10.1.2 The total degree of a graph is … ?
Even. By the Handshake Theorem it equals 2⋅2 \cdot2⋅ (number of edges), and the number of edges is an integer.
[Graphs: Definitions and Basic Properties] Is there a graph with four vertices of degrees 1, 1, 2 and 3?
No. The total degree would be 1+1+2+3=71 + 1 + 2 + 3 = 71+1+2+3=7 , which is odd, but the total degree of every graph is even.
[Graphs: Definitions and Basic Properties] Is there a graph with four vertices of degrees 1, 1, 3 and 3?
Yes. Each of these graphs has deg(a)=deg(b)=1\deg(a) = \deg(b) = 1deg(a)=deg(b)=1 and deg(c)=deg(d)=3\deg(c) = \deg(d) = 3deg(c)=deg(d)=3 .
[Graphs: Definitions and Basic Properties] Is there a simple graph with four vertices of degrees 1, 1, 3 and 3?
No. Let deg(c)=deg(d)=3\deg(c) = \deg(d) = 3deg(c)=deg(d)=3 . Without loops and parallel edges, ccc must be adjacent to all three other vertices, and so must ddd . Then the other two vertices a,ba, ba,b are both adjacent to ccc and ddd , so deg(a)≥2\deg(a) \ge 2deg(a)≥2 , a contradiction with deg(a)=1\deg(a) = 1deg(a)=1 .
[Graphs: Definitions and Basic Properties] Is it possible in a group of nine people for each to be friends with exactly five others?
No. In the graph with people as vertices and an edge for each pair of friends, every vertex would have degree 5, so the total degree would be 9⋅5=459 \cdot 5 = 459⋅5=45 , which is odd. But the total degree of a graph is even.
[Graphs: Definitions and Basic Properties] Proposition 10.1.3 In any graph, the number of vertices of odd degree is … ?
Even. Example: in the path with edges {a,b}\{a, b\}{a,b} , {b,c}\{b, c\}{b,c} the degrees are 1,2,11, 2, 11,2,1 : two vertices of odd degree.
[Graphs: Definitions and Basic Properties] In any graph there is an even number of vertices of odd degree.How is this proved?
The degrees of the odd-degree vertices add up to O=T−EO = T - EO=T−E , which is even; a sum of nnn odd integers is even only if nnn is even. TTT is the total degree (even) and EEE is the sum of the degrees of the even-degree vertices (a sum of even numbers, so even).
[Graphs: Definitions and Basic Properties] Is there a graph with ten vertices of degrees 1, 1, 2, 2, 2, 3, 4, 4, 4 and 6?
No: it would have three vertices of odd degree (degrees 1, 1, 3). Every graph has an even number of vertices of odd degree. Equivalently, the total degree 1+1+2+2+2+3+4+4+4+6=291 + 1 + 2 + 2 + 2 + 3 + 4 + 4 + 4 + 6 = 291+1+2+2+2+3+4+4+4+6=29 is odd.
[Graphs: Definitions and Basic Properties] What is the complement G′G'G′ of a simple graph GGG ?
The simple graph with the same vertices as GGG , in which two distinct vertices are connected by an edge exactly when they are not connected in GGG . Example: GGG (top) has the edges {v1,v2},{v2,v3},{v2,v4}\{v_1, v_2\}, \{v_2, v_3\}, \{v_2, v_4\}{v1,v2},{v2,v3},{v2,v4} ; G′G'G′ (bottom) has the other three edges {v1,v3},{v1,v4},{v3,v4}\{v_1, v_3\}, \{v_1, v_4\}, \{v_3, v_4\}{v1,v3},{v1,v4},{v3,v4} .
[Trails, Paths, and Circuits] What puzzle started graph theory, and who solved it, when?
The seven bridges of Königsberg, solved by Leonhard Euler in 1736. Question: can you walk around town, starting and ending at the same place, crossing each of the seven bridges exactly once? AAA , BBB , CCC , DDD are the land masses of Königsberg on the Pregel River.
[Trails, Paths, and Circuits] How did Euler turn the Königsberg bridge puzzle into a graph problem?
Each land mass becomes a vertex, each bridge an edge. The question becomes whether some route starts and ends at the same vertex and uses every edge exactly once.All points of one land mass can be identified, since you can go between them without crossing a bridge. Equivalently: can this graph be traced, starting and ending at the same point, without lifting the pencil?
[Trails, Paths, and Circuits] Why is there no route through the Königsberg graph that starts and ends at AAA and uses each edge exactly once?
Each pass through BBB , CCC or DDD uses two edges (one in, one out), so their degrees would have to be even, but deg(B)=5\deg(B) = 5deg(B)=5 , deg(C)=3\deg(C) = 3deg(C)=3 , deg(D)=3\deg(D) = 3deg(D)=3 . The same reasoning rules out starting at BBB , CCC or DDD , so the puzzle has no solution.
[Trails, Paths, and Circuits] GGG is a graph and v,wv, wv,w are vertices of GGG . What is a walk from vvv to www ?
A finite alternating sequence of adjacent vertices and edges v0e1v1e2⋯vn−1envnv_0 e_1 v_1 e_2 \cdots v_{n-1} e_n v_nv0e1v1e2⋯vn−1envn with v0=vv_0 = vv0=v , vn=wv_n = wvn=w , where vi−1v_{i-1}vi−1 and viv_ivi are the endpoints of eie_iei . Example: v1e1v2e2v3e4v3e3v2v_1 e_1 v_2 e_2 v_3 e_4 v_3 e_3 v_2v1e1v2e2v3e4v3e3v2 is a walk from v1v_1v1 to v2v_2v2 (here e4e_4e4 is a loop at v3v_3v3 ).
[Trails, Paths, and Circuits] The walk from vvv to vvv that consists of the single vertex vvv is the trivial walk.
It contains no edge.
[Trails, Paths, and Circuits] What is a trail from vvv to www ?
A walk from vvv to www that does not contain a repeated edge. Vertices may repeat. Example: v1e1v2e2v3e4v3v_1 e_1 v_2 e_2 v_3 e_4 v_3v1e1v2e2v3e4v3 is a trail; v3v_3v3 appears twice, but no edge does.
[Trails, Paths, and Circuits] What is a path from vvv to www ?
A trail from vvv to www that does not contain a repeated vertex. Example: v1e1v2e3v3v_1 e_1 v_2 e_3 v_3v1e1v2e3v3 is a path; v1e1v2e2v3e4v3v_1 e_1 v_2 e_2 v_3 e_4 v_3v1e1v2e2v3e4v3 is not ( v3v_3v3 repeats).
[Trails, Paths, and Circuits] A walk that starts and ends at the same vertex is a closed walk.
Example: v1e1v2e1v1v_1 e_1 v_2 e_1 v_1v1e1v2e1v1 is a closed walk (edges and vertices may repeat).
[Trails, Paths, and Circuits] What is a circuit?
A closed walk that contains at least one edge and does not contain a repeated edge. Example: in a graph with edges e1={a,b}e_1 = \{a, b\}e1={a,b} , e2={b,c}e_2 = \{b, c\}e2={b,c} , e3={c,a}e_3 = \{c, a\}e3={c,a} , the walk ae1be2ce3aa e_1 b e_2 c e_3 aae1be2ce3a is a circuit; ae1be1aa e_1 b e_1 aae1be1a is not ( e1e_1e1 repeats).
[Trails, Paths, and Circuits] What is a simple circuit?
A circuit that has no repeated vertex except the first and last. Other books call it a cycle.Example: abcaabcaabca in a triangle is a simple circuit; abcadeaabcadeaabcadea in two triangles sharing vertex aaa is a circuit but not simple ( aaa repeats in the middle).
[Trails, Paths, and Circuits] Walk, trail, path, closed walk, circuit, simple circuit: which of them must contain at least one edge?
Only circuits and simple circuits. So the trivial walk vvv is a closed walk (and a trail), but not a circuit.
[Trails, Paths, and Circuits] Walk, trail, path, closed walk, circuit, simple circuit: which of them may repeat an edge, and which may repeat a vertex?
Repeated edge: only walks and closed walks. Repeated vertex: all except paths and simple circuits (simple circuit: first and last only). Example: v1e1v2e1v1v_1 e_1 v_2 e_1 v_1v1e1v2e1v1 repeats edge e1e_1e1 , so it is a closed walk but not a circuit.
[Trails, Paths, and Circuits] Does the edge sequence e1e2e4e3e_1 e_2 e_4 e_3e1e2e4e3 specify a walk unambiguously? Does e1e_1e1 alone?
e1e2e4e3e_1 e_2 e_4 e_3e1e2e4e3 : yes, the walk v1e1v2e2v3e4v3e3v2v_1 e_1 v_2 e_2 v_3 e_4 v_3 e_3 v_2v1e1v2e2v3e4v3e3v2 . e1e_1e1 alone: no, it could be v1e1v2v_1 e_1 v_2v1e1v2 or v2e1v1v_2 e_1 v_1v2e1v1 .
[Trails, Paths, and Circuits] When is a walk in a graph GGG uniquely determined by its sequence of vertices?
Always, when GGG has no parallel edges. Example: here v2v3v_2 v_3v2v3 is ambiguous: it could be v2e2v3v_2 e_2 v_3v2e2v3 or v2e3v3v_2 e_3 v_3v2e3v3 . Example: here v1v2v2v3v_1 v_2 v_2 v_3v1v2v2v3 is unambiguous: v1e1v2e2v2e3v3v_1 e_1 v_2 e_2 v_2 e_3 v_3v1e1v2e2v2e3v3 .
[Trails, Paths, and Circuits] Classify as trail, path, circuit, simple circuit or just (closed) walk: (a) v1e1v2e3v3e4v3e5v4v_1 e_1 v_2 e_3 v_3 e_4 v_3 e_5 v_4v1e1v2e3v3e4v3e5v4 (b) e1e3e5e5e6e_1 e_3 e_5 e_5 e_6e1e3e5e5e6
(a) a trail from v1v_1v1 to v4v_4v4 , not a path. (b) just a walk from v1v_1v1 to v5v_5v5 . (a) has no repeated edge, but v3v_3v3 repeats. (b) repeats the edge e5e_5e5 .
[Trails, Paths, and Circuits] Classify as circuit or simple circuit: (c) v2v3v4v5v3v6v2v_2 v_3 v_4 v_5 v_3 v_6 v_2v2v3v4v5v3v6v2 (d) v2v3v4v5v6v2v_2 v_3 v_4 v_5 v_6 v_2v2v3v4v5v6v2
(c) a circuit, not simple. (d) a simple circuit. Both start and end at v2v_2v2 , have at least one edge and no repeated edge. In (c), v3v_3v3 repeats in the middle.
[Trails, Paths, and Circuits] Classify: (e) v1e1v2e1v1v_1 e_1 v_2 e_1 v_1v1e1v2e1v1 (f) v1v_1v1
(e) a closed walk, not a circuit. (f) a closed walk (and a trail), not a circuit. (e) repeats the edge e1e_1e1 . (f) contains no edge.
[Trails, Paths, and Circuits] Graph terminology is not standardized. What do other books often call what Epp calls a trail, a path, and a simple circuit?
Trail: "path"; path: "simple path"; simple circuit: "cycle". Also: Epp's graph is sometimes a "multigraph", Epp's simple graph a "graph", a vertex a "node", and an edge an "arc". Check definitions when reading other sources.
[Trails, Paths, and Circuits] When are two vertices vvv and www of a graph GGG connected, and when is the graph GGG connected?
vvv and www are connected if there is a walk from vvv to www . GGG is connected if every two vertices of GGG are connected. GGG is connected ⇔\Leftrightarrow⇔ ∀\forall∀ vertices v,w∈V(G)v, w \in V(G)v,w∈V(G) , ∃\exists∃ a walk from vvv to www .
[Trails, Paths, and Circuits] By negating the definition: when is a graph GGG not connected?
When there are two vertices of GGG that are not connected by any walk.
[Trails, Paths, and Circuits] Which of these graphs are connected?
Only (a). In (c), edges cross at a point that is not a vertex, so (c) is really three separate edges:
[Trails, Paths, and Circuits] Lemma 10.2.1(a) If a graph GGG is connected, then any two distinct vertices of GGG can be connected by … ?
a path. A walk between them exists by definition; the lemma says one can even be chosen with no repeated vertex.
[Trails, Paths, and Circuits] Lemma 10.2.1(b) Vertices vvv and www are part of a circuit in a graph GGG , and one edge is removed from the circuit. What still exists?
A trail from vvv to www in GGG . Example: in the circuit abcaabcaabca , remove the edge {a,b}\{a, b\}{a,b} : a,c,ba, c, ba,c,b is still a trail from aaa to bbb .
[Trails, Paths, and Circuits] Lemma 10.2.1(c) GGG is connected and contains a circuit. What can be removed from GGG without disconnecting GGG ?
An edge of the circuit. Example: a triangle abcaabcaabca stays connected when the edge {a,b}\{a, b\}{a,b} is removed: aaa and bbb are still joined through ccc .
[Trails, Paths, and Circuits] When is a graph HHH a connected component of a graph GGG ?
HHH is a connected subgraph of GGG of largest possible size: (1) HHH is a subgraph of GGG ; (2) HHH is connected; (3) no connected subgraph of GGG has HHH as a subgraph and contains vertices or edges not in HHH .Every graph is a kind of union of its connected components.
[Trails, Paths, and Circuits] Find all connected components of this graph GGG (vertex sets and edge sets).
V1={v1,v2,v3}V_1 = \{v_1, v_2, v_3\}V1={v1,v2,v3} , E1={e1,e2}E_1 = \{e_1, e_2\}E1={e1,e2} ; V2={v4}\ V_2 = \{v_4\} V2={v4} , E2=∅E_2 = \emptysetE2=∅ ; V3={v5,v6,v7,v8}\ V_3 = \{v_5, v_6, v_7, v_8\} V3={v5,v6,v7,v8} , E3={e3,e4,e5}E_3 = \{e_3, e_4, e_5\}E3={e3,e4,e5} . An isolated vertex alone forms a connected component.
[Trails, Paths, and Circuits] What is an Euler circuit for a graph GGG ?
A circuit that contains every vertex and every edge of GGG . So it has at least one edge, starts and ends at the same vertex, uses every vertex at least once and every edge exactly once.Example: in the triangle with vertices a,b,ca, b, ca,b,c , the circuit abcaabcaabca is an Euler circuit.
[Trails, Paths, and Circuits] Theorem 10.2.2 If a graph has an Euler circuit, then every vertex of the graph has … ?
positive even degree. Example: the Königsberg graph has vertices of degree 5, 3, 3 and 3, so it has no Euler circuit.
[Trails, Paths, and Circuits] If a graph has an Euler circuit, then every vertex has positive even degree.What is the key idea of the proof?
Going around the Euler circuit, each time you enter vvv along one edge, you leave along another edge, so the edges at vvv come in entry/exit pairs. Start in the middle of an edge, so that the start vertex also gets a pair. Every edge at vvv is used exactly once, so degv\deg vdegv is a positive multiple of 2. Euler circuit v0v1v2v3v4v5v0v_0 v_1 v_2 v_3 v_4 v_5 v_0v0v1v2v3v4v5v0 ; v2v_2v2 is entered and left twice, so degv2=4\deg v_2 = 4degv2=4 .
[Trails, Paths, and Circuits] Why does this graph have no Euler circuit?
v1v_1v1 and v3v_3v3 have degree 3, which is odd. Contrapositive of "Euler circuit ⇒\Rightarrow⇒ every vertex has positive even degree": if some vertex has odd degree, the graph has no Euler circuit.
[Trails, Paths, and Circuits] Is the converse true: if every vertex of a graph has even degree, must the graph have an Euler circuit?
No: the graph may be disconnected. Every vertex has degree 2, but no circuit contains both e1e_1e1 and e3e_3e3 .
[Trails, Paths, and Circuits] Theorem 10.2.3 If a graph GGG is … and the degree of every vertex of GGG is … , then GGG has an Euler circuit.
connected; a positive even integer. The proof is constructive: it contains an algorithm that finds the Euler circuit.
[Trails, Paths, and Circuits] GGG is connected and every vertex has positive even degree. What are the steps of the algorithm that builds an Euler circuit CCC (from the proof that such a graph has one)?
Step 1 Pick any vertex vvv of GGG . Step 2 Pick a sequence of adjacent vertices and edges that starts and ends at vvv and never repeats an edge: the circuit CCC . Step 3 If CCC contains every edge and vertex of GGG , stop: CCC is an Euler circuit. Otherwise do 3a to 3e. Step 3a Remove the edges of CCC from GGG , and the vertices that become isolated: the subgraph G′G'G′ . Step 3b Pick a vertex www that is in both CCC and G′G'G′ . Step 3c In G′G'G′ , pick a circuit C′C'C′ tha…
[Trails, Paths, and Circuits] GGG is a finite graph, and every vertex has positive even degree.Why does a walk from vvv that never repeats an edge always get back to vvv ?
Every vertex u≠vu \ne vu=v you enter has even degree, so an unused edge remains for leaving uuu . There are finitely many edges, so the walk must stop, and it can stop only at vvv .This is step 2 (and 3c) of the algorithm that builds an Euler circuit.
[Trails, Paths, and Circuits] Euler circuit algorithm, step 3a: remove the edges of the circuit CCC from GGG (every vertex of GGG having positive even degree), and remove the vertices that become isolated. Call the result G′G'G′ .Why does every vertex of G′G'G′ have positive even degree?
CCC uses an even number of edges at each vertex, and even minus even is even; the vertices of degree 0 were removed. CCC is drawn black, G′G'G′ blue; G′G'G′ need not be connected.
[Trails, Paths, and Circuits] Euler circuit algorithm, step 3b: pick a vertex www that lies both on the current circuit CCC and in the remaining graph G′G'G′ (the edges not in CCC ).Why does such a vertex www always exist?
Because GGG is connected: some edge not in CCC must have an endpoint on CCC , otherwise CCC and the rest of GGG would not be joined by any walk. Here there are two such vertices, uuu and www .
[Trails, Paths, and Circuits] Euler circuit algorithm: CCC is a circuit from vvv to vvv , and C′C'C′ is a circuit from www to www using edges not in CCC , where www lies on CCC .How are CCC and C′C'C′ combined into one circuit C′′C''C′′ ?
Follow CCC from vvv to www , then all of C′C'C′ back to www , then the rest of CCC back to vvv . C′′C''C′′ (black) uses all edges of CCC and C′C'C′ , each exactly once.
[Trails, Paths, and Circuits] Why does the algorithm that patches circuits together into an Euler circuit always stop?
Each round adds at least one new edge to CCC , and GGG has finitely many edges. When it stops, CCC contains every edge and vertex of GGG , so CCC is an Euler circuit.
[Trails, Paths, and Circuits] Find an Euler circuit starting at aaa with the algorithm: start with a circuit at aaa , then patch in circuits of unused edges.
For example abcdefheghjidaabcdefheghjidaabcdefheghjida . All degrees are 2 or 4 ( ddd , eee , hhh have degree 4), and the graph is connected. C=abcdaC = abcdaC=abcda ; it meets the rest at ddd : C′=deghjidC' = deghjidC′=deghjid , so C′′=abcdeghjidaC'' = abcdeghjidaC′′=abcdeghjida .It meets the rest at eee : C′=efheC' = efheC′=efhe , so C′′=abcdefheghjidaC'' = abcdefheghjidaC′′=abcdefheghjida , which uses all 13 edges.
[Trails, Paths, and Circuits] Theorem 10.2.4 A graph GGG has an Euler circuit if, and only if, … ?
GGG is connected and every vertex of GGG has positive even degree. ⇒\Rightarrow⇒ : an Euler circuit contains every vertex, so any two vertices are joined by part of it, and the entry/exit pairs make degrees even. ⇐\Leftarrow⇐ : the circuit-patching algorithm.
[Trails, Paths, and Circuits] GGG is a graph and v,wv, wv,w are two distinct vertices. What is an Euler trail from vvv to www ?
A walk from vvv to www that passes through every vertex of GGG at least once and uses every edge of GGG exactly once. Example: in the path graph a−b−ca - b - ca−b−c , abca b cabc is an Euler trail from aaa to ccc .
[Trails, Paths, and Circuits] Corollary 10.2.5 For distinct vertices vvv and www of a graph GGG , there is an Euler trail from vvv to www if, and only if, … ?
GGG is connected, vvv and www have odd degree, and all other vertices have positive even degree. Reason: adding a new edge {w,v}\{w, v\}{w,v} turns an Euler trail from vvv to www into an Euler circuit, so with that edge every degree is even; without it, vvv and www have odd degree.Example: the Königsberg graph has four odd vertices, so it has no Euler trail either.
[Trails, Paths, and Circuits] Is there a trail that starts in room AAA , ends in room BBB and goes through every interior doorway exactly once?
Yes, e.g. AGHFEIHEKJDCBAGHFEIHEKJDCBAGHFEIHEKJDCB . Rooms are vertices, doorways are edges. AAA and BBB have degree 1, every other vertex has even degree, and the graph is connected, so an Euler trail from AAA to BBB exists.
[Trails, Paths, and Circuits] What puzzle did Sir William Rowan Hamilton introduce in 1859?
A dodecahedron with a city at each vertex: start at one city, visit every other city exactly once along the edges, and return to the start. A dodecahedron is a solid with 12 identical pentagonal faces. Laid flat, one solution (black):
[Trails, Paths, and Circuits] A simple circuit that includes every vertex of a graph GGG is a Hamiltonian circuit for GGG .
Every vertex appears exactly once, except the first and the last, which are the same.Example: in K4K_4K4 with vertices a,b,c,da, b, c, da,b,c,d , the circuit abcdaabcdaabcda is a Hamiltonian circuit.
[Trails, Paths, and Circuits] Is an Euler circuit always a Hamiltonian circuit? Is a Hamiltonian circuit always an Euler circuit?
No and no: an Euler circuit may visit a vertex more than once; a Hamiltonian circuit need not use every edge. Example: in K4K_4K4 with vertices a,b,c,da, b, c, da,b,c,d , the Hamiltonian circuit abcdaabcdaabcda leaves out the edges {a,c}\{a, c\}{a,c} and {b,d}\{b, d\}{b,d} .
[Trails, Paths, and Circuits] Is there a simple criterion, like the one for Euler circuits, for deciding whether a graph has a Hamiltonian circuit?
No, and no efficient algorithm for finding one is known. For Euler circuits: connected and every vertex of positive even degree. For Hamiltonian circuits, there is only a technique that often shows that none exists.
[Trails, Paths, and Circuits] Proposition 10.2.6. If a graph GGG has a Hamiltonian circuit, then GGG has a subgraph HHH with which four properties?
HHH contains every vertex of GGG HHH is connected HHH has the same number of edges as vertices Every vertex of HHH has degree 2 HHH is formed by the vertices and edges of the Hamiltonian circuit (black):
[Trails, Paths, and Circuits] C:v0e1v1e2⋯vn−1envnC: v_0 e_1 v_1 e_2 \cdots v_{n-1} e_n v_nC:v0e1v1e2⋯vn−1envn is a Hamiltonian circuit of a graph GGG with at least two vertices, and HHH is the subgraph of its vertices and edges.Why does HHH have as many edges as vertices, and why does every vertex of HHH have degree 2?
The nnn edges e1,…,ene_1, \dots, e_ne1,…,en are distinct and so are the nnn vertices v1,…,vnv_1, \dots, v_nv1,…,vn ; each viv_ivi lies on exactly the two edges eie_iei and ei+1e_{i+1}ei+1 (and v0=vnv_0 = v_nv0=vn on e1e_1e1 and ene_nen ). HHH is connected because any two of its vertices lie on the circuit.
[Trails, Paths, and Circuits] Why does this graph have no Hamiltonian circuit?
A Hamiltonian circuit would give a subgraph HHH with degb=2\deg b = 2degb=2 , but none of the four edges at bbb can be left out. Without {a,b}\{a, b\}{a,b} , vertex aaa would have degree below 2 in HHH ; likewise for eee , ccc , ddd . So degb=4\deg b = 4degb=4 in HHH .Uses: a Hamiltonian circuit gives a subgraph HHH containing every vertex, connected, with as many edges as vertices, all of degree 2.
[Trails, Paths, and Circuits] What is a traveling salesman problem?
Finding a Hamiltonian circuit with the least total distance, in a graph whose edges are marked with distances.
[Trails, Paths, and Circuits] Distances in km. A salesman starts at AAA , visits each other city exactly once and returns to AAA . Which route is shortest?
ABCDAABCDAABCDA (or ADCBAADCBAADCBA ): 125 km. ABCDAABCDAABCDA : 30+30+25+40=12530 + 30 + 25 + 40 = 12530+30+25+40=125 ; ABDCA\ ABDCA ABDCA : 30+35+25+50=14030 + 35 + 25 + 50 = 14030+35+25+50=140 ; ACBDA\ ACBDA ACBDA : 50+30+35+40=15550 + 30 + 35 + 40 = 15550+30+35+40=155 .The other three routes are these backwards.
[Trails, Paths, and Circuits] Why is listing all Hamiltonian circuits impractical for solving the traveling salesman problem on a complete graph with 30 vertices?
There are 29!/2≈4.42×103029!/2 \approx 4.42 \times 10^{30}29!/2≈4.42×1030 circuits from a fixed vertex; at one nanosecond each, that takes about 1.4×10141.4 \times 10^{14}1.4×1014 years. No more efficient exact algorithm is known, but efficient algorithms find "pretty good" circuits.
[Matrix Representations of Graphs] What is an m×nm \times nm×n matrix AAA over a set SSS ?
A rectangular array of elements of SSS arranged into mmm rows and nnn columns, written A=(aij)A = (a_{ij})A=(aij) . aija_{ij}aij , the entry in row iii and column jjj , is the ijijij th entry; m×nm \times nm×n is the size.Example: [10−34−15]\begin{bmatrix} 1 & 0 & -3 \\ 4 & -1 & 5 \end{bmatrix}[140−1−35] is a 2×32 \times 32×3 matrix over Z\mathbb{Z}Z with a23=5a_{23} = 5a23=5 .
[Matrix Representations of Graphs] When are two matrices A=(aij)A = (a_{ij})A=(aij) and B=(bij)B = (b_{ij})B=(bij) equal?
When they have the same size and all corresponding entries are equal: aij=bija_{ij} = b_{ij}aij=bij for all i,ji, ji,j .
[Matrix Representations of Graphs] What is a square matrix, and what is the main diagonal of an n×nn \times nn×n matrix AAA ?
Square: as many rows as columns. Main diagonal: the entries a11,a22,…,anna_{11}, a_{22}, \dots, a_{nn}a11,a22,…,ann .
[Matrix Representations of Graphs] A=[10−34−15−220]A = \begin{bmatrix} 1 & 0 & -3 \\ 4 & -1 & 5 \\ -2 & 2 & 0 \end{bmatrix}A=⎣⎡14−20−12−350⎦⎤ What is the entry in row 2, column 3? The second column? The main diagonal?
5; [0−12]\ \begin{bmatrix} 0 \\ -1 \\ 2 \end{bmatrix} ⎣⎡0−12⎦⎤ ; 1,−1,0\ 1, -1, 0 1,−1,0 .
[Matrix Representations of Graphs] GGG is a directed graph with ordered vertices v1,…,vnv_1, \dots, v_nv1,…,vn . What is the adjacency matrix A=(aij)A = (a_{ij})A=(aij) of GGG ?
The n×nn \times nn×n matrix with aija_{ij}aij = the number of arrows from viv_ivi to vjv_jvj . Example: A=[100112100]A = \begin{bmatrix} 1 & 0 & 0 \\ 1 & 1 & 2 \\ 1 & 0 & 0 \end{bmatrix}A=⎣⎡111010020⎦⎤ ; a23=2a_{23} = 2a23=2 (two arrows from v2v_2v2 to v3v_3v3 ).
[Matrix Representations of Graphs] In the adjacency matrix of a directed graph, what do a nonzero entry on the main diagonal and an entry larger than 1 show?
Nonzero aiia_{ii}aii : loops at viv_ivi . aij>1a_{ij} > 1aij>1 : parallel arrows from viv_ivi to vjv_jvj . Example: a11=1a_{11} = 1a11=1 means one loop at v1v_1v1 ; a23=2a_{23} = 2a23=2 means two arrows from v2v_2v2 to v3v_3v3 .
[Matrix Representations of Graphs] Find the adjacency matrix of this directed graph.
[000011210]\boldsymbol{\begin{bmatrix} 0 & 0 & 0 \\ 0 & 1 & 1 \\ 2 & 1 & 0 \end{bmatrix}}⎣⎡002011010⎦⎤ Row 1 is all 0: no arrows leave v1v_1v1 . Renumbering the vertices would move the rows and columns around.
[Matrix Representations of Graphs] Draw a directed graph with adjacency matrix A=[0110110200112100]A = \begin{bmatrix} 0 & 1 & 1 & 0 \\ 1 & 1 & 0 & 2 \\ 0 & 0 & 1 & 1 \\ 2 & 1 & 0 & 0 \end{bmatrix}A=⎣⎡0102110110100210⎦⎤ .
Vertices v1,…,v4v_1, \dots, v_4v1,…,v4 , with aija_{ij}aij arrows from viv_ivi to vjv_jvj : e.g. a41=2a_{41} = 2a41=2 : two arrows from v4v_4v4 to v1v_1v1 ; a22=1a_{22} = 1a22=1 : a loop at v2v_2v2 . The matrix does not determine the edge labels, so the graph is not unique.
[Matrix Representations of Graphs] GGG is an undirected graph with ordered vertices v1,…,vnv_1, \dots, v_nv1,…,vn . What is the adjacency matrix A=(aij)A = (a_{ij})A=(aij) of GGG ?
The n×nn \times nn×n matrix with aija_{ij}aij = the number of edges connecting viv_ivi and vjv_jvj . A loop at viv_ivi adds 1 to aiia_{ii}aii .Example: for the triangle v1v2v3v_1 v_2 v_3v1v2v3 : A=[011101110]A = \begin{bmatrix} 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \end{bmatrix}A=⎣⎡011101110⎦⎤ .