CS453 Graph Theory Assignment 3

Description

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.