Hint for March 2018 DMMC Web Problem

Top solvers for the February 2018 DMMC Web Problem!

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\).

The special pentagon

You can use the drawing of \(A_{5,2}\) shown below to trace edge disjoint hamiltonian cycles by three-coloring the edges by hand.

Missing diagonal.

Top solvers for the February 2018 DMMC Web Problem!


Go to the original problem page

Back to the Detroit Mercy Math Competition page.