Graph Theory Assignment 3 Solution

Description

1. Recall that the handshaking lemma says that the total degree of a loopless graph is twice the number of edges. Also recall that has 2 vertices (each binary -tuple is a vertex) and that is -regular. How many edges does have?

2. Explain why a nontrivial simple finite graph cannot have a walk of maximum length, but it must have a path of maximum length.

3. A trail is a walk that does not repeat an edge. Prove that a trail that repeats a vertex must contain a cycle. (Think about the set of nontrivial sub-walks along the trail that start and end at the same vertex.)

4. Here are two 3-regular graphs, both with six vertices and nine edges. If they are isomorphic, give an explicit isomorphism : → . If they are not isomorphic, provide a convincing argument for this fact (for instance, point out a structural feature of one that is not shared by the other.)

5. Below is depicted a graph constructed by joining two opposite vertices of ₁₂. Some authors call this a “theta graph” because it resembles the Greek letter .

1. What is the total degree of this graph?

2. What are the possible total degrees of graphs obtained by deleting a vertex of ?

3. What are the possible total degrees of graphs obtained by contracting an edge of ?

4. What are the possible total degrees of graphs obtained by identifying two vertices of ?