Graph Coloring

Determine if a graph is 2-colorable using graph traversal.

graph bipartite bfs coloring

Write a function `can_color_graph(n, edges)` that receives the number of vertices `n` (vertices are labeled from 0 to n-1) and a list of undirected edges `edges`, where each edge is a pair `(a, b)`. The graph is not necessarily connected. Return `True` if the graph is bipartite (i.e., 2-colorable) and `False` otherwise. The graph is 2-colorable if you can assign each vertex a color (either 0 or 1) such that every edge connects two vertices of different colors. You may assume there are no self-loops or duplicate edges.

Constraints

- 1 <= n <= 10^3
- 0 <= len(edges) <= 10^4
- Each edge is a pair of distinct integers in range [0, n-1].
- The graph is undirected.
- Expected time complexity O(n + len(edges)), space O(n + len(edges)).

Example

```python
>>> can_color_graph(4, [(0,1), (1,2), (2,3)])
True
>>> can_color_graph(3, [(0,1), (1,2), (0,2)])
False
```

20 points ~20 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Start by building an adjacency list from the edges.

Use BFS or DFS to traverse each connected component; assign alternating colors (0 and 1).

If you ever try to color a neighbor with the same color as the current vertex, the graph is not 2-colorable.

Remember to handle disconnected components — you must check every component.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.