MathCastle
Graph TheoryHardGraphs and Degrees

Graphs and Degrees · Hard problem

A network planner proposes a list of degrees for 1212 computers: five of them listed as degree 33 and the other seven as degree 44. Exactly 55 of the 1212 proposed degrees are odd. By the handshake lemma's corollary (the number of odd-degree vertices in any simple graph is always even), this list cannot be realized. What is the SMALLEST number of entries in the list that must be changed by exactly 11 (up or down) to remove this obstruction?