[SOLVED] CPTS553 Assignment 5

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 𝐺 = 𝐶₃ × 𝐶₃ 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.

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

3. 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 ℓ₁ and ℓ₂?)
4. What is the value of ℓ in the “theta” graph (𝐶₈ with an extra edge) below?

1. What is the value of ℓ for 𝐾₅, the complete graph on 5 vertices?