《Mathematics for Computer》Lecture l8 graphs1

6.042/18.] Mathematics for Computer Science March 1. 2005 Srini devadas and Eric Lehman Lecture notes Graph Theory 1 Introduction normally, a graph is a bunch of dots connected by lines. Here is an example of a graph B H D A F E Sadly, this definition is not precise enough for mathematical discussion. Formally, a graph is a pair of sets(V, E), where v is a nonempty set whose elements are called vertices E is a collection of two-element subsets of V called edges The vertices correspond to the dots in the picture, and the edges correspond to the lines Thus, the dots-and-lines diagram above is a pictorial representation of the graph(V,e whe V=A, B,C, D,E, F, G, H, II E={{A,B},{A,C},{B,D},{C,D},{C,E},{E,F},{E,G},{H,I}} 1.1 Definitions A nuisance in first learning graph theory is that there are so many definitions. They all correspond to intuitive ideas, but can take a while to absorb. Some ideas have multi- le names. For example, graphs are sometimes called networks, vertices are sometimes called nodes, and edges are sometimes called arcs. Even worse no one can agree on the exact meanings of terms. For example, in our definition, every graph must have at least one vertex. However, other authors permit graphs with no vertices. (The graph with

6.042/18.062J Mathematics for Computer Science March 1, 2005 Srini Devadas and Eric Lehman Lecture Notes Graph Theory 1 Introduction Informally, a graph is a bunch of dots connected by lines. Here is an example of a graph: A B C D E F G H I Sadly, this definition is not precise enough for mathematical discussion. Formally, a graph is a pair of sets (V, E), where: • V is a nonempty set whose elements are called vertices. • E is a collection of two­element subsets of V called edges. The vertices correspond to the dots in the picture, and the edges correspond to the lines. Thus, the dots­and­lines diagram above is a pictorial representation of the graph (V, E) where: V = {A, B, C, D, E, F, G, H, I} E = {{A, B} , {A, C} , {B, D} , {C, D} , {C, E} , {E, F} , {E, G} , {H, I}} . 1.1 Definitions A nuisance in first learning graph theory is that there are so many definitions. They all correspond to intuitive ideas, but can take a while to absorb. Some ideas have multi￾ple names. For example, graphs are sometimes called networks, vertices are sometimes called nodes, and edges are sometimes called arcs. Even worse, no one can agree on the exact meanings of terms. For example, in our definition, every graph must have at least one vertex. However, other authors permit graphs with no vertices. (The graph with

Graph th no vertices is the single stupid counterexample to many would-be theorems so we 're banning it! )This is typical; everyone agrees more-or-less what each term means, but dis Hereafter, we use A-B to denote an edge between vertices A and b rather than the set notation(A, B]. Note that A-B and B-A are the same edge, just as (A, B) and(B, A] are the same set Two vertices in a graph are said to be adjacent if they are joined by an edge, and an edge is said to be incident to the vertices it joins. The number of edges incident to a vertex is called the degree of the vertex. For example, in the graph above, A is adjacent to B and B is adjacent to D, and the edge A-C is incident to vertices A and C. Vertex H has degree 1, D has degree 2, and E has degree 3 Deleting some vertices or edges from a graph leaves a subgraph. Formally, a subgraph G=(V, E)is a graph G=(V,E) where V subset of v and e is subset of E. Since a subgraph is itself a graph, the endpoints of every edge in E' must be vertices in v/ 1.2 Sex in america A 1994 University of Chicago study entitled The Social Organization of Sexuality found that on average men have 74% more opposite-gender partners than women Let's recast this observation in graph theoretic terms. Let G=(V, e)be a graph where the set of vertices V consists of everyone in America. Now each vertex either represents either a man or a woman so we can partition v into two subsets: M, which contains all the male vertices and w, which contains all the female vertices. Let' s draw all the M vertices on the left and the W vertices on the right Now, without getting into a lot of specifics, sometimes an edge appears between an M vertex and a w vertex

2 Graph Theory no vertices is the single, stupid counterexample to many would­be theorems— so we’re banning it!) This is typical; everyone agrees more­or­less what each term means, but dis￾agrees about weird special cases. So do not be alarmed if definitions here differ subtly from definitions you see elsewhere. Usually, these differences do not matter. Hereafter, we use A—B to denote an edge between vertices A and B rather than the set notation {A, B}. Note that A—B and B—A are the same edge, just as {A, B} and {B, A} are the same set. Two vertices in a graph are said to be adjacent if they are joined by an edge, and an edge is said to be incident to the vertices it joins. The number of edges incident to a vertex is called the degree of the vertex. For example, in the graph above, A is adjacent to B and B is adjacent to D, and the edge A—C is incident to vertices A and C. Vertex H has degree 1, D has degree 2, and E has degree 3. Deleting some vertices or edges from a graph leaves a subgraph. Formally, a subgraph of G = (V, E) is a graph G� = (V � , E� ) where V � is a nonempty subset of V and E� is a subset of E. Since a subgraph is itself a graph, the endpoints of every edge in E� must be vertices in V � . 1.2 Sex in America A 1994 University of Chicago study entitled The Social Organization of Sexuality found that on average men have 74% more opposite­gender partners than women. Let’s recast this observation in graph theoretic terms. Let G = (V, E) be a graph where the set of vertices V consists of everyone in America. Now each vertex either represents either a man or a woman, so we can partition V into two subsets: M, which contains all the male vertices, and W, which contains all the female vertices. Let’s draw all the M vertices on the left and the W vertices on the right: M W Now, without getting into a lot of specifics, sometimes an edge appears between an M vertex and a W vertex:

Graph ti Since were only considering opposite-gender relationships, every edge connects an M vertex on the left to a w vertex on the right. So the sum of the degrees of the M vertices must equal the sum of the degrees of the w vertices x∈M y∈W Now suppose we divide both sides of this equation by the product of the sizes of the two sets,|M|·|W ∑ IEM deg(a).1/∑ Yew deg().1 The terms above in parentheses are the average degree of an M vertex and the average degree ofa w vertex. So we know: Avg deg in M Avg deg in w avg deg in w\Avg deg in w M Now the Census Bureau reports that there are slightly more women than men in Amer- ica; in particular WI/M is about 1.035. So- assuming the Census Bureau is correct- weve just proved that the University of Chicago study got bad data! On average, men have 3.5% more opposite-gender partners. Furthermore, this is totally unaffected by dif- ferences in sexual practices between men and women; rather, it is completely determined by the relative number of men and women 1.3 Graph variations There are many variations on the basic notion of a graph. Three particularly common variations are described below. In a multigraph, there may be more than one edge be- tween a pair of vertices. Here is an example

� � Graph Theory 3 M W Since we’re only considering opposite­gender relationships, every edge connects an M vertex on the left to a W vertex on the right. So the sum of the degrees of the M vertices must equal the sum of the degrees of the W vertices: deg(x) = deg(y) x∈M y∈W Now suppose we divide both sides of this equation by the product of the sizes of the two sets, |M| · |W|: �� � �� � x∈M deg(x) 1 y∈W deg(y) 1 · = W| · |M| | |W| |M| The terms above in parentheses are the average degree of an M vertex and the average degree of a W vertex. So we know: Avg. deg in M Avg. deg in W = |W| |M| W Avg. deg in M = | | · Avg. deg in W |M| Now the Census Bureau reports that there are slightly more women than men in Amer￾ica; in particular |W / M | | | is about 1.035. So— assuming the Census Bureau is correct— we’ve just proved that the University of Chicago study got bad data! On average, men have 3.5% more opposite­gender partners. Furthermore, this is totally unaffected by dif￾ferences in sexual practices between men and women; rather, it is completely determined by the relative number of men and women! 1.3 Graph Variations There are many variations on the basic notion of a graph. Three particularly common variations are described below. In a multigraph, there may be more than one edge be￾tween a pair of vertices. Here is an example:

Graph Theory The edges in a directed graph are arrows pointing to one endpoint or the other. Here an exampl t Directed graphs are often called digraphs. We denote an edge from vertex A to vertex in a digraph by A- B. Formally, the edges in a directed graph ed are ordere Pairs of vertices rather than sets of two vertices. The number of edges directed into a vertex is called the in-degree of the vertex, and the number of edged directed out is called the out-degree One can also allow self-loops, edges with both endpoints at one vertex. He re is an example of a graph with self-loops Combinations of these variations are also possible for example, one could work with directed multigraphs with self-loops Except where stated otherwise, the word"graph" in this course refers to a graph without mul- tiple edges, directed edges, or self-loops

4 Graph Theory The edges in a directed graph are arrows pointing to one endpoint or the other. Here is an example: Directed graphs are often called digraphs. We denote an edge from vertex A to vertex B in a digraph by A −→ B. Formally, the edges in a directed graph are ordered pairs of vertices rather than sets of two vertices. The number of edges directed into a vertex is called the in­degree of the vertex, and the number of edged directed out is called the out­degree. One can also allow self­loops, edges with both endpoints at one vertex. Here is an example of a graph with self­loops: Combinations of these variations are also possible; for example, one could work with directed multigraphs with self­loops. Except where stated otherwise, the word “graph” in this course refers to a graph without mul￾tiple edges, directed edges, or self­loops

Graph theor 1.4 Applications of graphs Graphs are the most useful mathematical objects in computer science. You can model an enormous number of real-world systems and phenomena using graphs. Once you've created such a model, you can tap the vast store of theorems about graphs to gain insight into the system you're modeling. Here are some practical situations where graphs arise Data Structures Each vertex represents a data object. There is a directed edge from one object to another if the first contains a pointer or reference to the second Attraction Each vertex represents a person, and each edge represents a romantic attrac- tion. The graph could be directed to model the unfortunate asymmetries Airline Connections Each vertex represents an airport. If there is a direct flight be- tween two airports, then there is an edge between the corresponding vertices. These graphs often appear in airline magazines The Web Each vertex represents a web page. Directed edges between vertices represent People often put numbers on the edges of a graph, put colors on the vertices, or add other ornaments that capture additional aspects of the phenomenon being modeled. For example, a graph of airline connections might have numbers on the edges to indicate the duration of the corresponding flight. The vertices in the attraction graph might be colored to indicate the person s gender 1.5 Some Common graphs Some graphs come up so frequently that they have names. The complete graph on n vertices, also called Kn, has an edge between every pair of vertices. Here is K The empty graph has no edges at all. Here is the empty graph on 5 vertices

Graph Theory 5 1.4 Applications of Graphs Graphs are the most useful mathematical objects in computer science. You can model an enormous number of real­world systems and phenomena using graphs. Once you’ve created such a model, you can tap the vast store of theorems about graphs to gain insight into the system you’re modeling. Here are some practical situations where graphs arise: Data Structures Each vertex represents a data object. There is a directed edge from one object to another if the first contains a pointer or reference to the second. Attraction Each vertex represents a person, and each edge represents a romantic attrac￾tion. The graph could be directed to model the unfortunate asymmetries. Airline Connections Each vertex represents an airport. If there is a direct flight be￾tween two airports, then there is an edge between the corresponding vertices. These graphs often appear in airline magazines. The Web Each vertex represents a web page. Directed edges between vertices represent hyperlinks. People often put numbers on the edges of a graph, put colors on the vertices, or add other ornaments that capture additional aspects of the phenomenon being modeled. For example, a graph of airline connections might have numbers on the edges to indicate the duration of the corresponding flight. The vertices in the attraction graph might be colored to indicate the person’s gender. 1.5 Some Common Graphs Some graphs come up so frequently that they have names. The complete graph on n vertices, also called Kn, has an edge between every pair of vertices. Here is K5: The empty graph has no edges at all. Here is the empty graph on 5 vertices:

Graph Theory Here is a path with 5 vertices And here is a cycle with 5 vertices, which is typically denoted Cs g Paths and cycles are going to be particularly important, so lets define them precisely. path is a graph P=(V, E)of the form V=u1, U2,..., Un) E={1-t2,v2-t3,,tn-1-n} where n> l and vertices v1,..., Un are all distinct. Vertices u and Un are the endpoints of the path. Note that a path may consist of a single vertex, in which case both endpoints are the same. We'll often say that there is a path from u to u in a graph G; this is a shorthand for saying that a path with endpoints u and u is a subgraph of g Similarly, a cycle is a graph C=(V, E) of the form E={t-02,t2-t3,,tn-1-tn,tn-t} where n>3 and U1,..., Un are all distinct. The length of a path or cycle is the number of edges it contains. For example, a path with 5 vertices has length 4, but a cycle with 5 vertices has length 5

6 Graph Theory Here is a path with 5 vertices: And here is a cycle with 5 vertices, which is typically denoted C5: Paths and cycles are going to be particularly important, so let’s define them precisely. A path is a graph P = (V, E) of the form V = {v1, v2, . . . , v E n} = {v1 —v2, v2 —v3, . . . , vn−1 —vn} where n ≥ 1 and vertices v1, . . . , vn are all distinct. Vertices v1 and vn are the endpoints of the path. Note that a path may consist of a single vertex, in which case both endpoints are the same. We’ll often say that there is a path from u to v in a graph G; this is a shorthand for saying that a path with endpoints u and v is a subgraph of G. Similarly, a cycle is a graph C = (V, E) of the form V = {v1, v2, . . . , v E n} = {v1 —v2, v2 —v3, . . . , vn−1 —vn, vn —v1} where n ≥ 3 and v1, . . . , vn are all distinct. The length of a path or cycle is the number of edges it contains. For example, a path with 5 vertices has length 4, but a cycle with 5 vertices has length 5

Graph theor 1.6 Isomorphism Two graphs that look the same might actually be different in a formal sense. For example the two graphs below are both cycles with 4 vertices A D But one graph has vertex set (A, B, C, D) while the other has vertex set (1, 2, 3, 4) If so, then the graphs are different mathematical objects, strictly speaking. But this is a frustrating distinction; the graphs look the same! Fortunately, we can neatly capture the idea of looks the same"and use that as our main notion of equivalence between graphs Graphs G1 and G2 are isomorphic if there exists a one-to-one correspondence between vertices in G1 and vertices in G2 such that there is an edge between two vertices in G1 if and only if there is an edge between the two corresponding vertices in G2. For example, take the following correspondence between vertices in the two graphs above A corresponds to 1 B corresponds to 2 D corresponds to 4 C corresponds to 3 Now there is an edge between two vertices in the graph on the left if and only if there is an edge between the two corresponding vertices in the graph on the right. Therefore, the two graphs are isomorphic. The correspondence itself is called an isomorphism Two isomorphic graphs may be drawn to look quite different. For example, here are two different ways of drawing Cs Isomorphic graphs share a great many properties, such as the number of vertices, number of edges, and the pattern of vertex degrees. Thus, two graphs can be proved

Graph Theory 7 1.6 Isomorphism Two graphs that look the same might actually be different in a formal sense. For example, the two graphs below are both cycles with 4 vertices: A B D C 1 2 4 3 But one graph has vertex set {A, B, C, D} while the other has vertex set {1, 2, 3, 4}. If so, then the graphs are different mathematical objects, strictly speaking. But this is a frustrating distinction; the graphs look the same! Fortunately, we can neatly capture the idea of “looks the same” and use that as our main notion of equivalence between graphs. Graphs G1 and G2 are isomorphic if there exists a one­to­one correspondence between vertices in G1 and vertices in G2 such that there is an edge between two vertices in G1 if and only if there is an edge between the two corresponding vertices in G2. For example, take the following correspondence between vertices in the two graphs above: A corresponds to 1 B corresponds to 2 D corresponds to 4 C corresponds to 3. Now there is an edge between two vertices in the graph on the left if and only if there is an edge between the two corresponding vertices in the graph on the right. Therefore, the two graphs are isomorphic. The correspondence itself is called an isomorphism. Two isomorphic graphs may be drawn to look quite different. For example, here are two different ways of drawing C5: Isomorphic graphs share a great many properties, such as the number of vertices, number of edges, and the pattern of vertex degrees. Thus, two graphs can be proved

Graph Theory nonisomorphic by identifying some property that one possesses that the other does not For example, if one graph has two vertices of degree 5 and another has three vertices of degree 5, then the graphs can not be isomorphic 2 Connectivity In the diagram below, the graph on the left has two pieces, while the graph on the right has just one Let's put this observation in rigorous terms. a graph is connected if for every pair of vertices u and v, the graph contains a path with endpoints u and v as a subgraph The graph on the left is not connected because there is no path from any of the top three vertices to either of the bottom two vertices. However, the graph on the right is connected, because there is a path between every pair of vertices A maximal, connected subgraph is called a connected component(By"maximal",we mean that including any additional vertices would make the subgraph disconnected. The graph on the left has two connected components, the triangle and the single edge The graph on the right is entirely connected and thus has a single connected component 2.1 A Simple Connectivity Theorem The following theorem says that a graph with few edges must have many connected components Theorem 1. Every graphG=(V, E)has at least V-E connected components Proof. We use induction on the number of edges. Let P(n)be the proposition that ever graphG=(V, E)with El=n has at least V1-n connected components Base case: In a graph with 0 edges, each vertex is itself a connected component, and so there are exactly V-0=V connected components Inductive step: Now we assume that the induction hypothesis holds for every n-edge graph in order to prove that it holds for every(n+ 1)-edge graph, where n >0. Con sider a graphG=(V, E)with n+ 1 edges. Remove an arbitrary edge u-v and call the

8 Graph Theory nonisomorphic by identifying some property that one possesses that the other does not. For example, if one graph has two vertices of degree 5 and another has three vertices of degree 5, then the graphs can not be isomorphic. 2 Connectivity In the diagram below, the graph on the left has two pieces, while the graph on the right has just one. Let’s put this observation in rigorous terms. A graph is connected if for every pair of vertices u and v, the graph contains a path with endpoints u and v as a subgraph. The graph on the left is not connected because there is no path from any of the top three vertices to either of the bottom two vertices. However, the graph on the right is connected, because there is a path between every pair of vertices. A maximal, connected subgraph is called a connected component. (By “maximal”, we mean that including any additional vertices would make the subgraph disconnected.) The graph on the left has two connected components, the triangle and the single edge. The graph on the right is entirely connected and thus has a single connected component. 2.1 A Simple Connectivity Theorem The following theorem says that a graph with few edges must have many connected components. Theorem 1. Every graph G = (V, E) has at least |V | − |E| connected components. Proof. We use induction on the number of edges. Let P(n) be the proposition that every graph G = (V, E) with |E| = n has at least | | V − n connected components. Base case: In a graph with 0 edges, each vertex is itself a connected component, and so there are exactly |V | − 0 = | | V connected components. Inductive step: Now we assume that the induction hypothesis holds for every n­edge graph in order to prove that it holds for every (n + 1)­edge graph, where n ≥ 0. Con￾sider a graph G = (V, E) with n + 1 edges. Remove an arbitrary edge u—v and call the

Graph ti resulting graph G. By the induction assumption, G has at least VI-n connected com ponents. Now add back the edge u-v to obtain the original graph G. If u and v were in the same connected component of G, then g has the same number of connected compo- nents as G, which is at least V-n. Otherwise, if u and v were in different connected components of G, then these two components are merged into one in G, but all other components remain. Therefore, G has at least n-1=V-(n+ 1)connected components The theorem follows by induction Corollary 2. Every connected graph with n vertices has at least n-1 edge A couple points about the proof of Theorem 1 are worth noting. First, notice that we used induction on the number of edges in the graph. This is very common in proofs involving graphs, and so is induction on the number of vertices. When you're pi resen with a graph problem, these two approachs should be among the first you consider. Dont try induction on other variables that crop up in the problem unless these two strategies seem hopeless The second point is more subtle. Notice that in the inductive step, we took an arbitrary (n 1)-edge graph, threw out an edge so that we could apply the induction assumption, and then put the edge back. You'll see this shrink-down, grow-back process very often in the inductive steps of proofs related to graphs. This might seem like needless effort; why not start with an n-edge graph and add one more to get an(n+ 1-edge graph? That would work fine in this case but opens the door to a very nasty logical error in similar arguments. (You'll see an example in recitation. Always use shrink-down, grow-back arguments, and you'll never fall into this trap 2.2 Distance and Diameter The distance between two vertices in a graph is the length of the shortest path between them. For example, the distance between two vertices in a graph of airline connections is the minimum number of flights required to travel between two cities

Graph Theory 9 resulting graph G� . By the induction assumption, G� has at least |V | − n connected com￾ponents. Now add back the edge u—v to obtain the original graph G. If u and v were in the same connected component of G� , then G has the same number of connected compo￾nents as G� , which is at least |V | − n. Otherwise, if u and v were in different connected components of G� , then these two components are merged into one in G, but all other components remain. Therefore, G has at least |V | − n − 1 = | | V − (n + 1) connected components. The theorem follows by induction. Corollary 2. Every connected graph with n vertices has at least n − 1 edges. A couple points about the proof of Theorem 1 are worth noting. First, notice that we used induction on the number of edges in the graph. This is very common in proofs involving graphs, and so is induction on the number of vertices. When you’re presented with a graph problem, these two approachs should be among the first you consider. Don’t try induction on other variables that crop up in the problem unless these two strategies seem hopeless. The second point is more subtle. Notice that in the inductive step, we took an arbitrary (n + 1)­edge graph, threw out an edge so that we could apply the induction assumption, and then put the edge back. You’ll see this shrink­down, grow­back process very often in the inductive steps of proofs related to graphs. This might seem like needless effort; why not start with an n­edge graph and add one more to get an (n + 1)­edge graph? That would work fine in this case, but opens the door to a very nasty logical error in similar arguments. (You’ll see an example in recitation.) Always use shrink­down, grow­back arguments, and you’ll never fall into this trap. 2.2 Distance and Diameter The distance between two vertices in a graph is the length of the shortest path between them. For example, the distance between two vertices in a graph of airline connections is the minimum number of flights required to travel between two cities. A B C D E F G H

Graph th In this graph, the distance between C and H is 2, the distance between G and C is 3, and the distance between a and itself is o. If there is no path between two vertices then the distance between them is said to be"infinit The diameter of a graph is the distance between the two vertices that are farthest apart The diameter of the graph above is 5. The most-distant vertices are A and G, which are at distance 5 from one another 2.2.1 Six Degrees of Separation There is an old claim that the world has only"six degrees of separation". In other if you pick any two on the planet- say a hermit in Montana and a rando son off the street in then the hermit knows someone who knows someone who knows someone who knows the Chinese pedestrian, where the word"knows"appears at most six times We can recast this in graph-theoretic terms. Consider a graph where the vertices are all the people on the planet, and there is an edge between two people if and only if they know each other. Then the"six degrees of separation"claim amounts to the assertion that the diameter of this graph is at most 6 There is little hope of proving or disproving the claim, since people are constantly be ing born, meeting one another, and dying and no one can keep track of who-knows-who However, precise data does exist for something similar. The University of Virginia main tains the Oracle of Bacon website. This is based on an"acting graph"where the vertices are actors and actresses, and there is an edge between two performers if they appeared in a movie together The website reports that everyone is within distance 8 of Kevin Bacon (This excludes a few actors who are completely disconnected. This allows us to at least obtain an upper bound on the diameter of the acting graph Theorem 3. Let v be an arbitrary vertex in a graph G. If every vertex is within distance d of u, then the diameter of the graph is at most 2d Proof. Let r and y be arbitrary vertices in the graph. Then there exists a path of length at most d from a to u, and there exists a path of length at most d from v to y Let z be the vertex that lies on both the x-to-U and u-to-y paths and is closest to r. (We know that such a vertex exists, since z could be v, at least. Joining the a-to-z segment to

10 Graph Theory In this graph, the distance between C and H is 2, the distance between G and C is 3, and the distance between A and itself is 0. If there is no path between two vertices, then the distance between them is said to be “infinity”. The diameter of a graph is the distance between the two vertices that are farthest apart. The diameter of the graph above is 5. The most­distant vertices are A and G, which are at distance 5 from one another. 2.2.1 Six Degrees of Separation There is an old claim that the world has only “six degrees of separation”. In other words, if you pick any two people on the planet— say a hermit in Montana and a random per￾son off the street in Beijing— then the hermit knows someone who knows someone who knows someone who knows the Chinese pedestrian, where the word “knows” appears at most six times. We can recast this in graph­theoretic terms. Consider a graph where the vertices are all the people on the planet, and there is an edge between two people if and only if they know each other. Then the “six degrees of separation” claim amounts to the assertion that the diameter of this graph is at most 6. There is little hope of proving or disproving the claim, since people are constantly be￾ing born, meeting one another, and dying and no one can keep track of who­knows­who. However, precise data does exist for something similar. The University of Virginia main￾tains the Oracle of Bacon website. This is based on an “acting graph” where the vertices are actors and actresses, and there is an edge between two performers if they appeared in a movie together. The website reports that everyone is within distance 8 of Kevin Bacon. (This excludes a few actors who are completely disconnected.) This allows us to at least obtain an upper bound on the diameter of the acting graph. Theorem 3. Let v be an arbitrary vertex in a graph G. If every vertex is within distance d of v, then the diameter of the graph is at most 2d. Proof. Let x and y be arbitrary vertices in the graph. Then there exists a path of length at most d from x to v, and there exists a path of length at most d from v to y. x y v z Let z be the vertex that lies on both the x­to­v and v­to­y paths and is closest to x. (We know that such a vertex exists, since z could be v, at least.) Joining the x­to­z segment to