CS453 - Graph Theory - Assignment 3  - Solved

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.