CPTS 553 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 𝐶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 𝐺?