Bipartite Graphs

Question

Below is a BFS algorithm to determine if a graph is bipartite:

function isGraphBipartite(node, graph, visited, distance) {
    const queue = [node];
    distance[node] = 0; //Initial node's distance to itself is 0

    while (queue.length > 0) {
        
        let curNode = queue.shift();
        visited[curNode] = true; 
        
        for (let neighbor of graph[curNode]) {

            
            if(!visited[neighbor]) {
                visited[neighbor] = true;
                distance[neighbor] = distance[curNode] + 1;
                queue.push(neighbor);
            } else {
                if (distance[neighbor] === distance[curNode]) return false; //KEY LINE
            }
        }
    }
    return true;
}

var isBipartite = function(graph) {
    let visited = {};
    let distance = {};

    for (let vertex = 0; vertex < graph.length; vertex++) { 
        if(!visited[vertex]) { 
            if (!isGraphBipartite(vertex, graph, visited, distance)) return false;
        }
    }
    return true;
};

I know that a valid bigraph cannot have odd cycles. I also know that the presence of a same level cross edge in a graph will invalidate it as a bigraph.

Is there some sort of mathematical intuition/explanation/rationale where if (distance[neighbor] === distance[curNode]), that means that there is a same level cross edge which somehow generates an odd cycle?

Answer 1

If nodes A and B have paths to the root that are the same length, then they are the same distance from the node at which those paths diverge. If A and B are also neighbors, then they form a cycle with that vertex of length 2*distance+1, which is odd.

So, any edges between nodes at the same distance from the root indicate that the graph is not bipartite. Also, since adjacent nodes' distance from the root can differ by at most 1, only those edges indicate odd cycles. When those edges don't exist, all edges connect nodes in even-numbered BFS levels to nodes in odd-numbered BFS levels, and that is the bipartite partition.