Problem 0. Properties of Graphs.

Use the Lab page Properties of Graphs to learn or to remind yourself of the definitions of the diameter of a graph, of complete, cycle, grid, path, star and wheel graphs, and of the conditions under which a graph is connected, regular, planar and/or bipartite. When you want to return to this page, use the Back option of your browser, not the Previous button given on Properties of Graphs.

The list below gives a number of true statements (in bold; these you don't have to prove), and asks some questions. Please answer each question.

All complete graphs, cycle graphs, grid graphs, path graphs, star graphs and wheel graphs are connected.

All cycle graphs, grid graphs, path graphs, star graphs and wheel graphs are planar.

Question: Is a complete graph K_n ever planar?

Answer:

All complete graphs and cycle graphs are regular, but only two star graphs, and only one wheel graphs are regular.

Question: Can you identify these special wheel graphs and star graphs?

Answer:

Question: Which grid graphs are regular? And which wheel graphs?

Answer:

The diameter of a complete graph is always 1.

Question: What is the diameter of a path graph P_n? And that of a cycle graph C_n? Or a grid graph G_m,n?

Answer:

Question: Show that the diameter of a star graph S_n for n > 1 or a wheel graph W_n for n > 4 is always 2.

Answer:

All grid graphs, path graphs, and star graphs are bipartite.

Question: Can you identify the two special sets of vertices in each of these cases?

Answer:

Question: Which cycle graphs are bipartite? And which complete graphs? Wheel graphs?

Answer:

Problem 1. Directed and Undirected Graphs.

Answer:

Problem 2. Sum of Degrees

(a) Draw three small graphs (4-10 edges apiece), and for each vertex, write the degree next to the vertex.

(b) For each of the three graphs in part (a), add up the degrees of the vertices in that graph. Note that the sum for each graph is even.

(c) Explain why for any graph, the sum of the degrees of the vertices is always even.

(a) Draw a three small (8-15 vertices) trees:

(b) For each of the three trees in part (a), count the number of vertices V and the number of edges E. Note that V-E=1 for each tree.

(c) Explain why for any tree, V-E must always be equal to 1.

Problem 4. Forms of Butane

Butane molecules can be represented by trees with four vertices (this represents the carbon atoms, which are the interesting ones--the location of hydrogen atoms can be filled in by any competent chemist). We consider two forms of butane the same if and only if their corresponding graphs are isomorphic. How many different forms of butane are there? (I.e., how many non-isomorphic trees with four vertices are there?) Draw all the distinct forms (draw each distinct form only once!) and explain why there can be no others.

Problem 5. Forms of Pentane and Hexane

(a) Pentane molecules can be represented by trees with five vertices. We consider two forms of pentane the same if and only if their corresponding graphs are isomorphic. Draw all the distinct forms of pentane (each distinct form only once!) and count how many you have.

(b) Hexane molecules can be represented by trees with six vertices, where the maximum allowed degree for a vertex is 4. (Carbon can only form 4 bonds--this rule is also applicable to butane and pentane above, but they have so few carbon atoms that this question never arises.) We consider two forms of hexane the same if and only if their corresponding graphs are isomorphic. Draw all the distinct forms of hexane (each distinct form only once!) and count how many you have.

Problem 6. The Chinese Postman Problem

In class, we briefly touched on a simplified version of the Chinese Postman Problem, a close cousin of the Koenigsberg bridge problem that was studied by the Chinese mathematician Meigu Guan in the 1960s. We will now explore the original Chinese Postman Problem.

On his first day on the job, a new postman is given the map below and instructed that he must deliver letters to houses along each of the streets on the map. The postman wants to find the shortest possible route that includes each of the streets on the map at least once and returns him to his starting point at the post office (the intersection in the upper lefthand corner).

a) Draw the graph corresponding to the given map. Vertices in your graph will represent intersections and edges will represent the streets that connect pairs of intersections.

b) Add a weight to each edge to represent the length of the corresponding street.

c) Since the postman must travel each street at least once and return to his starting point, an Eulerian cycle, if it exists, will be the shortest possible route. Is it possible to find such a cycle for this graph? Use the result of Euler discussed in class to explain why or why not.

d) Add a new edge parallel to an existing edge (that is, connecting the same two vertices as an existing edge) in such a way that you make an Eulerian cycle possible. Verify that you can now find an Eulerian cycle in the graph.

e) How would the postman actually travel the route represented by your Eulerian cycle? In particular, since the postman can't build new streets, how does he travel your new edge?

f) In view of your answer to (e), what should the weight of your new edge be?

g) Find the total distance the postman needs to travel to complete the route represented by your new Eulerian cycle. Is this route the shortest route that satisfies the postman's constraints? If yes, explain why. If not, find a shorter route.

h) Now consider the following example:

How many ways are there to add 2 parallel edges to this graph so as to make an Eulerian cycle possible? Which way creates the shortest possible Eulerian cycle?

i) Using what you've learned, explain how in general a postman can find the shortest route that includes each street at least once and ends at his starting point.

Problem 7. Bacon Numbers

Six Degrees of Kevin Bacon is a popular trivia game whose name is a play on the phrase "six degrees of separation" , referring to the theory that anyone on earth can be connected to anyone else through a string of at most six acquaintances. In it, each player is given the name of an actor or actress and must try to connect that person to Kevin Bacon in six links or less. A link consists of naming an actor or actress who was in a movie with the last named actor or actress. So for example, if we were given Audrey Hepburn on our turn, we might say Audrey Hepburn was in Robin & Marian with Sean Connery, Sean Connery was in Entrapment with Catherine Zeta-Jones, Catherine Zeta-Jones was in The Terminal with Tom Hanks, and Tom Hanks was in Apollo 13 with Kevin Bacon for a total of four links.

a) Explain the connection between the Six Degrees of Kevin Bacon game and the Erdös number described in class.

b) Pick an actor or actress and try to connect them to Kevin Bacon, as if playing a turn of the Six Degrees of Kevin Bacon game. (You may find the Internet Movie Database at http://www.imdb.com/ a useful resource.)

In 1996, Brett Tjaden, then a graduate student in computer science at the University of Virginia, actually studied this phenomenon and found that most actors or actresses have "Bacon numbers" of only 2 or 3. In fact, the average Bacon number for all of the quarter million actors in the Internet Movie Database is 2.94. Moreover, all actors who can be connected to Kevin Bacon can be linked to him in 8 steps or less!

c) Relate this discovery to the small world phenomenon discussed in class. What can you say about the diameter of this graph? (Be careful. It is not 8.)

d) In the process of studying this phenomenon, Tjaden created a website called The Oracle of Bacon at Virginia to help people find the shortest linking paths. Visit this website at http://www.cs.virginia.edu/oracle/. Try finding the shortest path to Kevin Bacon for the actor or actress you chose in part (b). How does this new path compare to the path you found in part (b)? Also pick 2 additional actors or actresses and find their shortest paths to Kevin Bacon using the Oracle.

e) Are the Bacon numbers of these actors or actresses larger or smaller than you would have expected? Explain your answer.

f) Use the Star Links feature on the Oracle of Bacon website to find shortest paths between each pair of actors you can make from the three you chose above. Using this and the results from part (d), draw a graph showing how each pair out of the 4 actors (Kevin Bacon and the three you chose) are connected. Label each vertex in your graph with the actor's name and each edge with the name of the movie. (You do not have to connect the actors you use as intermediate steps with each other.)

Problem C1. Heptane

Heptane molecules can be represented by trees with seven vertices, where the maximum allowed degree for a vertex is 4. (Carbon can only form 4 bonds.) We consider two forms of heptane the same if and only if their corresponding graphs are isomorphic. Draw all the forms of heptane and count how many you have.

Problem C2. Octane

Octane molecules can be represented by trees with eight vertices, where the maximum allowed degree for a vertex is 4. (Carbon can only form 4 bonds.) We consider two forms of octane the same if and only if their corresponding graphs are isomorphic. Draw all the forms of octane and count how many you have.

Suppose 55 people attend a business meeting together. During the meeting, some pairs of them meet each other for the first time and shake hands. However, no one shakes hands with the same person more than once and of course no one can shake his/her own hand. Is it necessarily true that two people at the meeting shook the same number of hands? Explain your answer.