# 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.