Determine Whether an Undirected Graph Is Two-Colorable

Problem Statement

You are given an undirected graph with n vertices labeled from 0 to n - 1, and a list of undirected edges edges where each edges[i] = [u, v] represents an edge between vertex u and vertex v.

A graph is two-colorable (or bipartite) if each vertex can be assigned one of two colors such that no two adjacent vertices have the same color.

Write a function that returns True if the graph is two-colorable, and False otherwise.

Note that the graph may contain:

• Multiple disconnected components.
• Isolated vertices (vertices with degree 0).
• Self-loops (an edge connecting a vertex to itself).
• Parallel edges (multiple edges connecting the same pair of vertices).

Function Signature

def is_two_colorable(n: int, edges: list[list[int]]) -> bool:
    pass

Input & Output Format

• Input:
  • n: An integer representing the number of vertices.
  • edges: A list of lists of two integers, representing the undirected edges.
• Output: A boolean (True or False).

Constraints

• 1 <= n <= 10^5
• 0 <= len(edges) <= 2 * 10^5
• 0 <= edges[i][0], edges[i][1] < n

Examples

Example 1

Input: n = 4, edges = [[0, 1], [1, 2], [2, 3], [3, 0]]
Output: True
Explanation: We can color vertices 0 and 2 with color 0, and vertices 1 and 3 with color 1. No two adjacent nodes have the same color.

Example 2

Input: n = 3, edges = [[0, 1], [1, 2], [2, 0]]
Output: False
Explanation: This forms a triangle (odd cycle). It cannot be colored with two colors without a conflict.

Example 3

Input: n = 4, edges = [[0, 1], [1, 1]]
Output: False
Explanation: Vertex 1 has a self-loop, which immediately violates the condition because vertex 1 is adjacent to itself.

Edge Cases to Consider

• Graphs with self-loops (u == v), which are never two-colorable.
• Disconnected graphs with multiple independent components or isolated vertices.
• Large sparse graphs where recursive DFS might exceed standard recursion depth limits.