CS453 Graph Theory Assignment 5

Description

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.
00 01 02
10 11 12
20 21 22
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:
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.
00 01 02
10 11
11
12
20 21 22
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?