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 ๐บ?
