Q: Hamiltonian cycle in shared-digit graph Let G be a graph.
The Vertices of g are the possible trios made out of the numbers 1-7.
123 124 etc (total of 7 choose 3).
Two vertices have an edge between them if and only if the have one and only one digit in common.
Is there a Hamiltonian cycle? Prove your answer!

A: The graph consists of $\binom{7}{3} = 35$ vertices, and each vertex is adjacent to exactly $3\binom{4}{2} = 18$ other vertices. This means that the sum of the degrees of any two non-adjacent vertices is $36$, so by Ore's theorem, the graph has a Hamiltonian cycle.

A: G has a Hamiltonian cycle:
123-145-126-134-125-136-124-135-127-146-137-156-147-234-256-157-235-246-167-236-245-237-345-247-346-567-347-456-357-467-257-367-457-267-356-123
The choice of path mostly consists of the earliest available node (other than the start node), but with a little juggling and backtracking near the end. The graph is 18-regular ($3\times {4\choose 2}$), so I wasn't too concerned about running out of connections.
