Is Graph Bipartite?

A graph is bipartite if and only if it is 2-colorable

See Wikipedia page of Bipartite Graph

The idea is to use another caracterization of bipartite graph that stipulates that a graph is biparatite if and only if it is 2-colorable (ie two colors can be used to colors the graph with neighbours not having the same color).

1) For every subgraph (a graph possesses different subgraphs if some nodes are not reachable from other nodes), set a color to the first encountered node and then try to color other node with the rule that two neighbours should have different colors.

2) If two neighbours have the same colors hence the graph is not bipartite.

# check if the graph is 2-colorable as bipartite <=> 2-colorable
def isBipartite(graph: List[List[int]]) -> bool:
    color = {} # store colors used for each node

    # check if we can find a correct coloration for nodes linked to i wrt to already colored nodes
    # using only 2 colors as a bipartite graph is 2-colorable
    def dfs(i):
        for j in graph[i]:
            if j in color:
                # if same color as neighbour then graph is not 2-colorable
                if color[i] == color[j]:
                    return(False)
            else:
                # If bipartite, the graph is 2-colorable hence set neighbour to other color
                color[j] = 1 - color[i] 
                if not dfs(j):
                    return(False)
        return(True)

    # iterate over each node (to take into account non reachable node ie the different subgraphs of the graph)
    for i in range(len(graph)):
        if i not in color:
            color[i] = 0
            if not dfs(i):
                return(False)
    return(True)