CPTS553 Assignment 3 Solved

30.00 $ 15.00 $

Category:
Click Category Button to View Your Next Assignment | Homework

You'll get a download link with a: . zip solution files instantly, after Payment

Description

Rate this product

 

Questions with a (⋆) are each worth 1 bonus point for 453 students.

  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 𝑛.
    1. How many vertices does 𝐢𝑛 Γ— 𝐢𝑛 have?
    2. Show that 𝐢𝑛 Γ— 𝐢𝑛 is 4-regular. One way is to let (𝑝, π‘ž) be any vertex of 𝐢𝑛 Γ— 𝐢𝑛 and explicitly show that (𝑝, π‘ž) is adjacent to exactly four vertices.
    3. How many edges does 𝐢𝑛 Γ— 𝐢𝑛 have?

 

  1. We discuss Cartesian products of regular graphs more generally.
    1. Let 𝐺 be an π‘Ž-regular graph and 𝐻 be a 𝑏-regular graph. Show that 𝐺 Γ— 𝐻 is an (π‘Ž + 𝑏)-regular graph.
    2. (⋆) 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.

 

  1. Let 𝑄3 be the 3-cube with vertex set

𝑉 = {000,001,010,011,100,101,110,111}.

  1. Give an example of two vertices such that if we delete them both, the graph 𝐺 that remains is a 6-cycle.
  2. 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 𝐻?
  3. (⋆) What is the smallest number of edges we could delete from 𝑄3 so that the resulting graph is disconnected?Β  Justify your answer.

 

  1. Let 𝐺 be a graph with at least one edge.
    1. 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.
    2. 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.