Starting from:

$30

CPTS553- Graph Theory: Assignment 5 Solved

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?

More products