[SOLVED] CPTS553-Assignment 3

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 𝐺?