MathCastle
Graph TheoryMediumEulerian and Hamiltonian Graphs

Eulerian and Hamiltonian Graphs · Medium problem

A double-five domino set has 2121 dominoes (all pairs (i,j)(i,j) with 0≤i≤j≤50 \le i \le j \le 5). Model this as a multigraph with vertices 0,…,50,\ldots,5 and each domino as an edge. Each vertex initially has odd degree. What is the fewest dominoes that must be removed so that the remaining dominoes can be laid in a closed ring (forming an Euler circuit)?