Hint for March 2018 DMMC Web Problem
Top solvers for the February 2018 DMMC Web Problem!
- Mikhail Fedoseev, South Lyon High School
- Kathleen Springer, Huron High School
Hint for the March 2018 DMMC problem
View the original problem
With the help of the following three lemmas, the hamiltonian cycles of \(A_{5,2}\) become tractable.
Let \(A_{5,2}^{i,x}\) be the subgraph of \(A_{5,2}\) induced by vertices containing symbol \(1\leq i \leq 5\) in the first position, where \(x\in \{ 1,2,3,4,5 \}\setminus i\), then \(A_{5,2}^{i,x}\) is isomorphic to \(K_4\) a complete graph on 4 vertices. Top left graph in the figure below.
Contracting each of the 5 subgraphs \(A_{5,2}^{i,x}\) to a single vertex and removing loops and multiple edges, results in a complete graph on 5 vertices, that is a graph isomorphic to \(K_5\).
The graph \(K_5\) has two edge disjoint hamiltonian cycles. Top right graph in the figure below.
Use the two hamiltonian paths within each \(A_{5,2}^{i,x}\) to expand hamiltonian factors of \(K_5\) to two edge disjoint hamiltonian cycles in \(A_{5,2}\). Notice however that the remaining edges (shown in green) do not form a hamiltonian cycle, but instead form five 4-cycles (in this construction). So, something has to be modified. One suggestion is to also use of the second position of the vertex labels to obtain \(A_{5,2}^{y,j}\) with \(1\leq j \leq 5\) and \(y\in \{ 1,2,3,4,5 \}\setminus j\).
You can use the drawing of \(A_{5,2}\) shown below to trace edge disjoint hamiltonian cycles by three-coloring the edges by hand.
Top solvers for the February 2018 DMMC Web Problem!
- Mikhail Fedoseev, South Lyon High School
- Kathleen Springer, Huron High School
Go to the original problem page
Back to the Detroit Mercy Math Competition page.