Add Edges to Make Degrees of All Nodes Even

Add Edges to Make Degrees of All Nodes Even - Problem

There is an undirected graph consisting of n nodes numbered from 1 to n. You are given the integer n and a 2D array edges where edges[i] = [ai, bi] indicates that there is an edge between nodes ai and bi. The graph can be disconnected.

You can add at most two additional edges (possibly none) to this graph so that there are no repeated edges and no self-loops.

Return true if it is possible to make the degree of each node in the graph even, otherwise return false.

The degree of a node is the number of edges connected to it.

Input & Output

Example 1 — Basic Case

$ Input: n = 5, edges = [[1,2],[2,3],[3,4]]

› Output: true

💡 Note: Current degrees: [1,1,2,1,0]. Nodes 1,2,4 have odd degrees. We can add edges (1,4) and (5,2) to make all degrees even.

Example 2 — Already Valid

$ Input: n = 4, edges = [[1,2],[3,4]]

› Output: true

💡 Note: All nodes have degree 1 (odd). We have 4 odd nodes, so we can add edges (1,3) and (2,4) to make all degrees even.

Example 3 — Impossible Case

$ Input: n = 4, edges = [[1,2],[1,3],[1,4]]

› Output: false

💡 Note: Node 1 has degree 3, nodes 2,3,4 have degree 1. That's 4 odd nodes, but all pairs involve node 1, making it impossible with only 2 edges.

Constraints

1 ≤ n ≤ 10⁵
0 ≤ edges.length ≤ 10⁵
edges[i].length == 2
1 ≤ a_i, b_i ≤ n
a_i ≠ b_i
There are no repeated edges

Visualization

Tap to expand

Understanding the Visualization

Input Graph

Graph with some nodes having odd degrees

Count Analysis

Apply Handshaking Lemma to count odd nodes

Strategic Addition

Add at most 2 edges to make all degrees even

Key Takeaway

🎯 Key Insight: Use Handshaking Lemma - odd-degree node count is always even, enabling strategic pairing

Asked in

G Google 25 M Microsoft 18 a Amazon 15

The key insight is using the Handshaking Lemma: in any graph, the number of odd-degree vertices is always even. With at most 2 edge additions, we can only handle 0, 2, or 4 odd-degree nodes. Best approach uses mathematical analysis in O(n + m) time, O(n + m) space.

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Try All Possible Edge Additions	O(n³)	O(n)	Calculate degrees, find odd nodes, then try all possible ways to add 0, 1, or 2 edges
Mathematical Graph Theory Approach	O(n + m)	O(n + m)	Use the mathematical property that graphs always have an even number of odd-degree nodes

Brute Force - Try All Possible Edge Additions — Algorithm Steps

Step 1: Build degree array counting edges for each node
Step 2: Identify all nodes with odd degrees
Step 3: Try all combinations of adding 0, 1, or 2 edges
Step 4: Check if any combination makes all degrees even

Visualization

Tap to expand

Step-by-Step Walkthrough

Calculate Degrees

Count edges for each node

Find Odd Nodes

Identify nodes with odd degrees

Try Additions

Test all possible edge combinations

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

#define MAX_EDGES 1000

bool solution(int n, int edges[][2], int edgeCount) {
    // Calculate degrees
    int degree[n + 1];
    for (int i = 0; i <= n; i++) degree[i] = 0;
    
    // Store existing edges as strings
    char existingEdges[MAX_EDGES][20];
    int existingCount = 0;
    
    for (int i = 0; i < edgeCount; i++) {
        int a = edges[i][0], b = edges[i][1];
        degree[a]++;
        degree[b]++;
        sprintf(existingEdges[existingCount++], "%d,%d", a < b ? a : b, a < b ? b : a);
    }
    
    // Find odd degree nodes
    int oddNodes[n + 1];
    int oddCount = 0;
    
    for (int i = 1; i <= n; i++) {
        if (degree[i] % 2 == 1) {
            oddNodes[oddCount++] = i;
        }
    }
    
    // Case 1: Already all even
    if (oddCount == 0) {
        return true;
    }
    
    // Case 2: Try adding one edge
    if (oddCount == 2) {
        int a = oddNodes[0], b = oddNodes[1];
        char key[20];
        sprintf(key, "%d,%d", a < b ? a : b, a < b ? b : a);
        
        bool found = false;
        for (int i = 0; i < existingCount; i++) {
            if (strcmp(existingEdges[i], key) == 0) {
                found = true;
                break;
            }
        }
        
        if (a != b && !found) {
            return true;
        }
    }
    
    // Case 3: Try adding two edges
    if (oddCount == 4) {
        int pairs[3][2][2] = {
            {{oddNodes[0], oddNodes[1]}, {oddNodes[2], oddNodes[3]}},
            {{oddNodes[0], oddNodes[2]}, {oddNodes[1], oddNodes[3]}},
            {{oddNodes[0], oddNodes[3]}, {oddNodes[1], oddNodes[2]}}
        };
        
        for (int p = 0; p < 3; p++) {
            bool valid = true;
            for (int i = 0; i < 2; i++) {
                int a = pairs[p][i][0], b = pairs[p][i][1];
                char key[20];
                sprintf(key, "%d,%d", a < b ? a : b, a < b ? b : a);
                
                bool found = false;
                for (int j = 0; j < existingCount; j++) {
                    if (strcmp(existingEdges[j], key) == 0) {
                        found = true;
                        break;
                    }
                }
                
                if (a == b || found) {
                    valid = false;
                    break;
                }
            }
            if (valid) {
                return true;
            }
        }
    }
    
    return false;
}

int main() {
    int n;
    scanf("%d", &n);
    
    int edges[MAX_EDGES][2];
    int edgeCount = 0;
    
    char line[10000];
    scanf(" %[^\n]", line);
    
    // Simple parsing of [[a,b],[c,d]...]
    char *ptr = line + 1; // Skip first [
    while (*ptr && *ptr != ']') {
        if (*ptr == '[') {
            ptr++;
            edges[edgeCount][0] = atoi(ptr);
            while (*ptr && *ptr != ',') ptr++;
            ptr++; // Skip comma
            edges[edgeCount][1] = atoi(ptr);
            edgeCount++;
            while (*ptr && *ptr != ']') ptr++;
            ptr++; // Skip ]
        }
        ptr++;
    }
    
    bool result = solution(n, edges, edgeCount);
    printf(result ? "true\n" : "false\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n³)

Nested loops to try all possible pairs of nodes for edge additions

⚠ Quadratic Growth

Space Complexity

O(n)

Array to store degree of each node

⚡ Linearithmic Space

28.5K Views

Medium Frequency

~25 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Try All Possible Edge Additions — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler