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 12. Some authors call this a “theta graph” because it resembles the Greek letter .
A. What is the total degree of this graph?
B. What are the possible total degrees of graphs obtained by deleting a vertex of ?
C. What are the possible total degrees of graphs obtained by contracting an edge of ?
D. What are the possible total degrees of graphs obtained by identifying two vertices of ?
