Given an undirected graph graph that is represented by its adjacency matrix, return whether or not it is possible to add no more than two edges to this graph in order to make the degrees of nodes even.
Keep in mind that in the resulting graph there should be at most one edge between any pair of nodes.
Example:
graph = [[false, true, false, false],
[true, false, true, false],
[false, true, false, true],
[false, false, true, false]]The output should be solution(graph) = true.
The key idea is to count how many vertices have odd degree, since adding one edge flips the parity of exactly two endpoints. In an undirected simple graph, the answer is only possible when the number of odd-degree vertices is 0, 2, or 4. If it is 0, the graph is already valid. If it is 2, we can either connect the two odd vertices directly or use a third vertex that is not connected to either of them. If it is 4, we check the three possible pairings of the four odd vertices and see whether at least one pairing uses two missing edges. This makes the problem a small graph/parity check over the adjacency matrix.
