CPTS553 Assignment 5 Solved

30.00 $ 15.00 $

Click Category Button to View Your Next Assignment | Homework

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


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:







  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?