Why can't we determine if a graph is bipartite with simple iteration?

This is the problem I'm trying to solve

> We want to split a group of n people (labeled from 1 to n) into two groups of any size. Each person may dislike some other people, and they should not go into the same group.
Given the integer n and the array dislikes where dislikes[i] = [ai, bi] indicates that the person labeled ai does not like the person labeled bi, return true if it is possible to split everyone into two groups in this way.

This is solvable via BFS fairly trivially in Python:

def possibleBipartition(self, n: int, dislikes: List[List[int]]) -> bool:
    graph = defaultdict(set)
    for a, b in dislikes:
        graph[a-1].add(b-1)
        graph[b-1].add(a-1)

    q = deque({0})
    colors = [None]*n
    for i in range(n):
        if colors[i] is None:
            q = deque({i})
            colors[i] = 0
            while q:
                cur = q.popleft()
                for d in graph[cur]:
                    if colors[d] is None:
                        q.append(d)
                        colors[d] = 1 - colors[cur]
                    elif colors[d] == colors[cur]:
                        return False
    return True

However, when I try to do it in linear time with simple iteration, the algorithm fails

def possibleBipartition(self, n: int, dislikes: List[List[int]]) -> bool:
    graph = defaultdict(set)
    for a, b in dislikes:
        graph[a].add(b)
        graph[b].add(a)

    colors = {
        0: set(),
        1: set()
    }
    for i in range(n):
        if i in colors[0]:
            colors[1].update(graph[i])
        elif i in colors[1]:
            colors[0].update(graph[i])
        else:
            colors[0].add(i)
            colors[1].update(graph[i])

    return not (colors[0] & colors[1])

Why doesn't the second algorithm work and is there a way to solve this problem without some type of BFS/DFS/Union Find? I don't understand why the "recursive" algorithm is necessary. Why do we need to re-check old nodes rather than just comparing the sets?

Say this is your graph:

0 - 3 - 2 - 1

and you visit node 0 first, then 1. Your algorithm paints nodes 0 and 1 the same color, but those nodes need to be opposite colors.

Your algorithm assumes that if it doesn't already know what color a node needs to be, the node can be any color. That assumption is wrong, though. Unlike the breadth-first search, which forces the colors of all nodes connected to a node it visits, your code only forces the colors of a node's immediate neighbors, which isn't enough to avoid conflicting color assignments.