> For the complete documentation index, see [llms.txt](https://zedive.gitbook.io/project-l/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://zedive.gitbook.io/project-l/part-2/graph-search/graph-theory/bipartite_graph/is-the-graph-bipartite.md).

# Is the Graph Bipartite?

## Question ([LC.785](https://leetcode.com/problems/is-graph-bipartite/description/))

> Given a social network, divide people into two groups in which no one knows any other member in that group.

## Example

```
I: [[1,3], [0,2], [1,3], [0,2]]
O: true

I: [[1,2,3], [0,2], [0,1,3], [0,2]]
O: false
```

## Analysis

We can model the social network as an undirected graph. Then, we can use either DFS or BFS to determine the graph is bipartite or not.