Graph add at most 2 edges to make all graph nodes degree even

Given an undirected graph that is represented by its adjacency matrix, return whether or not is it possible to add no more than two edges to this graph in order to make all 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.

For

graph = [[false, true, false, false],
         [true, false, true, false],
         [false, true, false, true],
         [false, false, true, false]]

the output should be true.

This is my proposed broken solution:

boolean addEven(boolean[][] graph) {
    int odd = 0;
    int even = 0;
    for (int i = 0; i<graph.length; i++) {
        int k = 0;
        for (int j = 0; j<graph[0].length; j++) {
            if (graph[i][j] == true) {
                k++;
            }
        }
        if (k%2==1) {
            if (k == graph[0].length-1) {
                return false;
            }
            odd++;
        } else {
            even++;
        }
    }
    if (odd == 2 && even == 3) {
        return false;
    }
// Given that we have at most 2 new edges to be added the number of odd nodes should not be more than 2
    if (odd <=4) {
        return true;
    } else {
        return false;
    }
}

Your proposed "broken" solution is actually quite close to the actual solution. You don't need any well known algorithm to do it, but instead you have to notice the following things:

• Given that odd == 2, and the two odd vertices are $v,u$ - then we can "fix" them by either connecting them if they are not connected, or by finding another vertex $w$ such that $(v,w),(w,u)\notin G$ and then add the two edges.

• Given that odd == 4, the only way to "fix" them is by connecting them to each other, in 2 groups of 2: each edge on two different vertices.

Then, the actual code would look like this:
`boolean addEven(boolean[][] graph) {
int odd = 0;
List odd_vertices = new ArrayList();

for (int i = 0; i

Of course, this code is just to illustrate how the changes are reflected in the code. You can change it to be more general or optimize it, but I will keep it as is (especially because its hard to write code without a proper editor)

StackExchange Computer Science Q#135300, answer score: 3