CS453 - Graph Theory - Assignment 5  - Solved

1.     The graph 𝐺 = 𝐶3 × 𝐶3 is drawn below: 

 

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

b.     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 𝑃𝑛,𝑞 = 𝑃𝑛 × 𝑃𝑞. 

a.     Show that if either 𝑛 or 𝑞 is at least 3, then 𝑃𝑛,𝑞 is not Eulerian.  The easy way is to consider what happens along the boundary. 

b.     Show that for any 𝑞 ≥ 2, 𝑃2,𝑞 is Hamiltonian 

c.      Show that 𝑃4,4 is Hamiltonian.  The most straightforward way is to produce a Hamilton cycle. 

d.     Show that 𝑃3,3 is not Hamiltonian.  The drawing below may suggest a clever approach: 

 

                                                                                                                  02 

 

                                                                                                         12 

 

 

e.     If 𝑛 and 𝑞 are both odd, show that 𝑃𝑛,𝑞 is not Hamiltonian.  (Use the same clever argument from part d). 

f.       (⋆) 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. 

 

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

b.     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? 

c.      (⋆)  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?) 

d.      What is the value of ℓ in the “theta” graph (𝐶8 with an extra edge) below?   

 

 

 

 

 

 

 

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