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?
