Add Edges to Make Degrees of All Nodes Even

Add Edges to Make Degrees of All Nodes Even

What is this problem about?

This Hard difficulty Add Edges coding problem involves a graph where some nodes have an "odd degree" (an odd number of connected edges). You are allowed to add at most two new edges to the graph such that every node in the final graph has an even degree. You must determine if this is possible given the existing edges.

Why is this asked in interviews?

Uber and Quant firms ask this to test graph theory fundamentals. It requires understanding that in any graph, the number of odd-degree nodes is always even. By restricting the number of new edges to two, the problem becomes a case-study in combinatorial logic.

Algorithmic pattern used

This utilizes the Graph and Hash Table interview pattern.

1. Identify all nodes with odd degrees. If there are 0, it's already done. If there are more than 4, it's impossible (since 2 edges can fix at most 4 nodes).
2. Case 2 nodes: Try connecting them together or through an intermediate even-degree node.
3. Case 4 nodes: Try pairing them into two edges in all possible combinations.

Example explanation

Suppose nodes 1, 2, 3, and 4 are the only odd-degree nodes.

• Can we connect (1,2) and (3,4)? Only if those specific edges don't already exist.
• Can we connect (1,3) and (2,4)?
• Can we connect (1,4) and (2,3)? If any of these pairs work, return true.

Common mistakes candidates make

• Duplicate Edges: Forgetting that you cannot add an edge between two nodes if that edge already exists in the input.
• Odd Node Count: Failing to realize that if the number of odd nodes is odd (e.g., 1 or 3), it is mathematically impossible to fix the graph.
• Missing the "Intermediate" Case: For 2 odd nodes, forgetting that they could be fixed by connecting both to a single even-degree node they aren't already connected to.

Interview preparation tip

Always count the degrees of nodes first in graph problems. Parity (even vs. odd) is a frequent theme in advanced graph challenges.