Questions with a (โ) are each worth 1 bonus point for 453 students.
The graph ๐บ = ๐ถ3 × ๐ถ3 is drawn below: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.
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.
Now, for ๐, ๐ ≥ 2, consider the grid graph ๐๐,๐ = ๐๐ × ๐๐.Show that if either ๐ or ๐ is at least 3, then ๐๐,๐ is not Eulerian. The easy way is to consider what happens along the boundary.
Show that for any ๐ ≥ 2, ๐2,๐ is Hamiltonian
Show that ๐4,4 is Hamiltonian. The most straightforward way is to produce a Hamilton cycle.
Show that ๐3,3 is not Hamiltonian. The drawing below may suggest a clever approach:
02
12
If ๐ and ๐ are both odd, show that ๐๐,๐ is not Hamiltonian. (Use the same clever argument from part d).
(โ) If either ๐ or ๐ is even, show that ๐๐,๐ is Hamiltonian.
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.
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.
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?
(โ) 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?)
What is the value of โ in the “theta” graph (๐ถ8 with an extra edge) below?
What is the value of โ for ๐พ5, the complete graph on 5 vertices?
