Algorithm that check if given undirected graph can have Eulerian Cycle by adding edges

Question

Assume that G is a connectable undirected graph, what is the best algorithm in terms of complexity, that check if graph G can have an Eulerian cycle by adding edges?

I thought of their two cases

• G graph with odd number of vertices- then for sure it can have an Eulerian cycle becouse it is possible to transform the graph into a Clique by adding edges then the degree of all the edges is even - therefore the graph have an Eulerian Cycle
• G is graph with even number of vertices, therefore there is even number of vertices with odd degree and by connecting them in pairs, it is possible to transform the graph into even degree graph, then it for sure have a Eulerian Cycle. there is only one special case when there is a vertex that is connect to all the other vertices then, in such case it will be impossible to force the graph to have Eulerian Cycle

according to this prove i assume that the following algorithm that run in complexity of O(V), can check if graph can have Eulerian Cycle by adding edges

public static boolean hasCycle(ArrayList<Integer>[] graph){
    if(graph.length % 2 == 1)
        return true;

    for(ArrayList<Integer> vertex: graph) {
        // checking if the edge is connect to all the other vertex
        if (vertex.size() == graph.length - 1)
            return false;
    }

    return true;
}

the prove is correct? and what about the algorithm is also correct?

update

according to the answer i conclude that the following algorithm may work

public static boolean canHaveEualerenCycle(ArrayList<Integer>[] graph) {

    if(graph.length % 2 == 1)
        return true;

    Map<Integer, Set<Integer>> copy = new HashMap<>();

    for (int i = 0; i < graph.length; i++) {
        if (graph[i].size() % 2 == 1) {
            copy.put(i, new HashSet<>());
        }
    }

    // reveresing the graph odd vertex only
    for(Map.Entry<Integer, Set<Integer>> entry : copy.entrySet()) {
        entry.getValue().addAll(copy.keySet());
        entry.getValue().remove(entry.getKey());
        entry.getValue().removeAll(graph[entry.getKey()]);
    }


    // try to connect possible match of odd degree vertexes
    while (!copy.isEmpty()) {
        Map.Entry<Integer, Set<Integer>> entry = copy.entrySet().iterator().next();
        Set<Map.Entry<Integer, Set<Integer>>> edges = copy.entrySet();
        int vertexA = entry.getKey();

        if (!entry.getValue().isEmpty()) {
            int vertexB = entry.getValue().iterator().next();

            // vertexB is even degree now it is not an option any more
            for(Integer v : copy.get(vertexB)) {
                copy.get(v).remove(vertexB);
            }

            // vertexA is even degree now it is not an option any more
            for(Integer v : entry.getValue()) {
                copy.get(v).remove(vertexA);
            }

            copy.remove(vertexB);
            copy.remove(vertexA);
        } else {
            return false;
        }


    }

    return true;
}

but i am not sure 100% i didint find a way to prove that i have to connect odd degrees edges, maybe in a very complex graph it is not true.

Answer 1

Your algorithm is not always correct: for example, it will give a false positive for the graph below.

Here, the leftmost and rightmost vertices have odd degree, but you can't add an edge between them to fix that, because they already have an edge between them. Adding any other edges would bring one of the other vertices to degree $5$, so there's nothing to be done here.

In the case where $G$ has an even number of vertices, I have another suggestion. Rather than thinking about what edges we can add to $G$ to make all degrees even, think about what edges can be removed from the complementary graph $\overline{G}$ to make all of $\overline{G}$'s degrees odd.

Here, we can focus on each of the connected components of $\overline{G}$ separately. Once you do, there is a simple criterion for dealing with each connected component.