Graph add at most 2 edges to make all graph nodes degree even
Your proposed &quot;broken&quot; 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 &quot;fix&quot; 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 &quot;fix&quot; 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&lt;Integer&gt; odd_vertices = new ArrayList&lt;Integer&gt;();

    for (int i = 0; i &lt; graph.length; i++) {
        int deg = 0;
        for (int j = 0; j&lt;graph[0].length; j++) {
            if (graph[i][j] == true) {
                deg++;
            }
        }
        if (deg % 2 == 1) {
            odd++;
            odd_vertices.add(i);
        }
    }
// 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 == 0) {
        return true;
    } else if (odd == 2) {
        int a = odd_vertices.get(0);
        int b = odd_vertices.get(1);
        for (int k = 0; k &lt; graph.length; k++) {
            if (!graph[a][k] &amp;&amp; !graph[b][k]){
                return true;
            }
        }
        return false;
    } else if (odd == 4) {
        int a = odd_vertices.get(0);
        int b = odd_vertices.get(1);
        int c = odd_vertices.get(2);
        int d = odd_vertices.get(3);
        if ((!graph[a][b] &amp;&amp; !graph[c][d]) ||
            (!graph[a][c] &amp;&amp; !graph[b][d]) ||
            (!graph[a][d] &amp;&amp; !graph[b][c])) {
            
           return true;
        }
        return false;
    } else {
        return false;
}

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)