A common mistake for 3.4 was to say that when building a labeling using DFS/BFS and checking for inconsistencies as you go, there is always the same inconsistency would be found. This is not true: see the example below. It is not even clear what it means that "an inconsistency exists, and so BFS will find it", since which edge gives an error is different depending on the order of nodes in the BFS.

Example: nodes 1,2,3,4 in a cycle, with all edges being "same" except for (4,1). If we start BFS from node 2, then go to node 3, then node 1, then node 4, we get a labeling of all "A", and an error when we get to node 4. If instead we start with node 1, then node 4, then node 2, then node 3, we get a labeling which has both "A" and "B", and an error when considering node 3