3
$\begingroup$

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;
    }
}
$\endgroup$
5
  • $\begingroup$ This is an easy exercise. What did you try? $\endgroup$
    – Steven
    Feb 9, 2021 at 19:36
  • $\begingroup$ I tried to work on counting the number of nodes with odd and even degrees but I found 2 edge cases where my logic is not working... I feel that I am missing some well-known algorithm knowledge or the right approach to look at the problem $\endgroup$
    – jubecca
    Feb 9, 2021 at 19:50
  • $\begingroup$ I think you might have better luck getting an answer if you show what you got so far and describe where you got stuck. You can do so by editing the question. $\endgroup$
    – Steven
    Feb 9, 2021 at 20:08
  • $\begingroup$ Thanks, I added it! $\endgroup$
    – jubecca
    Feb 9, 2021 at 22:05
  • $\begingroup$ (A fine case for not writing, never presenting uncommented code.) $\endgroup$
    – greybeard
    Feb 10, 2021 at 8:23

1 Answer 1

3
$\begingroup$

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:

  1. 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.
  2. 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<Integer> odd_vertices = new ArrayList<Integer>();

    for (int i = 0; i < graph.length; i++) {
        int deg = 0;
        for (int j = 0; j<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 < graph.length; k++) {
            if (!graph[a][k] && !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] && !graph[c][d]) ||
            (!graph[a][c] && !graph[b][d]) ||
            (!graph[a][d] && !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)

$\endgroup$
2
  • $\begingroup$ Thanks for your answer! There is only one thing missing if (odd==0) return true. In case we don't need to add any edge. :) $\endgroup$
    – jubecca
    Feb 10, 2021 at 1:06
  • 1
    $\begingroup$ Thanks for letting me know, I added it in the solution. $\endgroup$
    – nir shahar
    Feb 10, 2021 at 12:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.