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!
2026-03-26 21:07:19.1774559239
On
Hamiltonian cycle in shared-digit graph
47 Views Asked by Bumbble Comm https://math.techqa.club/user/bumbble-comm/detail At
2
There are 2 best solutions below
1
On
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.
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.