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 to10 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