1. Let ๐ ≥ 3 be given and let ๐ถ๐ be the ๐-cycle whose vertices are {0,1,2,… , ๐ − 1}. Recall that ๐๐ is an edge if and only if ๐ = ๐ + 1 mod ๐ or ๐ = ๐ + 1 mod ๐.
a. How many vertices does ๐ถ๐ × ๐ถ๐ have?
b. Show that ๐ถ๐ × ๐ถ๐ is 4-regular. One way is to let (๐, ๐) be any vertex of ๐ถ๐ × ๐ถ๐ and explicitly show that (๐, ๐) is adjacent to exactly four vertices.
c. How many edges does ๐ถ๐ × ๐ถ๐ have?
2. We discuss Cartesian products of regular graphs more generally.
a. Let ๐บ be an ๐-regular graph and ๐ป be a ๐-regular graph. Show that ๐บ × ๐ป is an (๐ + ๐)-regular graph.
b. (โ) Let ๐บ be an ๐-regular graph. Show that ๐บ๐ (this is the ๐-fold cartesian product ๐บ × ๐บ × โฏ × ๐บ) is a ๐๐-regular graph. If you use mathematical induction, you may assume that ๐บ๐ is isomorphic to ๐บ × ๐บ๐−1.
3. Let ๐3 be the 3-cube with vertex set
๐ = {000,001,010,011,100,101,110,111}.
a. Give an example of two vertices such that if we delete them both, the graph ๐บ that remains is a 6-cycle.
b. Suppose we start with ๐3 and produce the graph ๐ป by identifying vertices 000 and 011; we call the resulting vertex ๐ค. What is the degree of ๐ค in ๐ป?
c. (โ) What is the smallest number of edges we could delete from ๐3 so that the resulting graph is disconnected? Justify your answer.
4. Let ๐บ be a graph with at least one edge.
a. Show that for any ๐ ≥ 1, if ๐ is a walk in ๐บ of length ๐, then there exists a walk ๐′ in ๐บ of length ๐ + 1. This shows that ๐บ cannot have a longest walk.
b. Show that there is some upper bound ๐ on the length of a path in ๐บ. This means that if ๐ is a walk of length ๐ > ๐, then a vertex must be repeated in ๐. This shows that ๐บ must have a
longest path.
