Starting from:

$25

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? 

  

 

More products