Skip to content
Hello Python

Validate a Bipartite Graph

Practice ExerciseIntermediateMediumGraphQueueBipartite Check

Checking your account…

Sign in to save your code and progress across devices. The lesson and problem statement remain public.

Loading the interactive Practice workspace.If it does not appear, the problem and learning material remain readable, but browser execution is unavailable.Reload Practice workspace

Problem

Implement is_bipartite(node_count, edges). Return whether every undirected edge connects nodes with opposite colors.

Starter code

def is_bipartite(node_count, edges):
    pass
Test cases

square

{
  "args": [
    4,
    [
      [
        0,
        1
      ],
      [
        1,
        2
      ],
      [
        2,
        3
      ],
      [
        3,
        0
      ]
    ]
  ]
}

Expected: true

triangle

{
  "args": [
    3,
    [
      [
        0,
        1
      ],
      [
        1,
        2
      ],
      [
        2,
        0
      ]
    ]
  ]
}

Expected: false

Wizard outline
  1. Step 1: Start every node uncolored

    Represent an undirected graph with no color assignments. Bipartite validation assigns one of two colors only when traversal reaches a node.

  2. Step 2: Alternate colors through one component

    Use BFS from node 0 and reject a same-color edge. Each traversed edge must connect opposite colors.

  3. Step 3: Validate disconnected components

    Start a fresh two-color BFS at every uncolored node. Every connected component has an independent starting color.

Footguns and prerequisites
  • Coloring only one component misses a disconnected odd cycle.
  • Recoloring an already colored node can hide a contradiction.
  • trees and graphs
Reviewed references
Recommended approach and implementation

Breadth-first color each component, assigning opposite colors across every edge.

Why it works: Each discovered edge enforces opposite endpoint colors. A conflict proves an odd cycle; if all edges satisfy the rule, the two color classes form a valid bipartition.

def is_bipartite(node_count, edges):
    from collections import deque
    graph = [[] for _ in range(node_count)]
    for left, right in edges:
        graph[left].append(right); graph[right].append(left)
    colors = [-1] * node_count
    for start in range(node_count):
        if colors[start] != -1:
            continue
        colors[start] = 0
        queue = deque([start])
        while queue:
            node = queue.popleft()
            for neighbor in graph[node]:
                if colors[neighbor] == -1:
                    colors[neighbor] = 1 - colors[node]; queue.append(neighbor)
                elif colors[neighbor] == colors[node]:
                    return False
    return True