# CPTS553 Assignment 5 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

Assignment 5

Due at 5:00 pm on Monday, October 11 Questions with a (β) are each worth 1 bonus point for 453 students.

1. The graph πΊ = πΆ3 Γ πΆ3 is drawn below:
1. Show that πΊ is Eulerian. The suggested way is to use the characterization we discussed in class.Β  The not-so-easy way is to actually produce an Euler circuit; if you choose this latter route, it suffices to list the vertices in order as theyβd be encountered in the circuit.
2. Show that πΊ is Hamiltonian. Here, youβll want to produce a Hamilton cycle.Β  Again, it suffices to list the vertices in order as theyβd be encountered in the cycle.

1. Now, for π, π β₯ 2, consider the grid graph ππ,π = ππ Γ ππ.
1. Show that if either π or π is at least 3, then ππ,π is not Eulerian. The easy way is to consider what happens along the boundary.
2. Show that for any π β₯ 2, π2,π is Hamiltonian
3. Show that π4,4 is Hamiltonian. The most straightforward way is to produce a Hamilton cycle.
4. Show that π3,3 is not Hamiltonian. The drawing below may suggest a clever approach:

02

12

1. If π and π are both odd, show that ππ,π is not Hamiltonian. (Use the same clever argument from part d).
2. (β) If either π or π is even, show that ππ,π is Hamiltonian.

1. Recall that if a graph πΊ has no links (this means every edge of πΊ is a bridge), then there is a relationship among π, π, and π. Here, π is the number of components, π is the number of edges, and π is the number of vertices in the graph πΊ.

We now consider when πΊ has links.

1. What is the relationship among π, π, π if deleting any 1 link of πΊ turns every other link into a bridge (Example: πΊ is a cycle)? Consider the effect of deleting a link.
2. Now, suppose πΊ is a graph where you can arrive at an all-bridge graph by deleting β links, one at a time, taking care not to delete any edges that become bridges in this process. What is the relationship among π, π, π now?
3. (β) Show that for any graph πΊ, there is a unique value β that works in part π.Β  (What would happen if there were two such values β1 and β2?)
4. What is the value of β in the βthetaβ graph (πΆ8 with an extra edge) below?

1. What is the value of β for πΎ5, the complete graph on 5 vertices?