Graph TheoryHardGraphs and Degrees
Graphs and Degrees · Hard problem
A network planner proposes a list of degrees for computers: five of them listed as degree and the other seven as degree . Exactly of the 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 (up or down) to remove this obstruction?