Questions with a (⋆) are each worth 1 bonus point for 453 students. 1. The graph 𝐺 = 𝐶3 × 𝐶3 is drawn below:
00 01
02
12
22
|
10 |
11 |
|
20 |
21 |
- 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.
2. Now,for𝑛,𝑞≥2,considerthegridgraph𝑃 =𝑃 ×𝑃. 𝑛,𝑞 𝑛 𝑞
- 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, 𝑃 is Hamiltonian
- Show that 𝑃 is Hamiltonian. The most straightforward way is to 4,4
produce a Hamilton cycle.
- Show that 𝑃 is not Hamiltonian. The drawing below may suggest a
3,3
clever approach:
2,𝑞
00 01
02
12
22
is not Hamiltonian. (Use the
|
10 |
11 |
|
11 20 |
21 |
- If 𝑛 and 𝑞 are both odd, show that 𝑃 𝑛,𝑞
same clever argument from part d).
- (⋆) 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.
- 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 l 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 l that works in part 𝑏. (What would happen if there were two such values l1 and l2?)
- What is the value of l in the “theta” graph (𝐶8 with an extra edge) below?
- What is the value of l for 𝐾 , the complete graph on 5 vertices? 5
