B.5.QD:5.1 - From a false graph claim to a construction or obstruction

An engineer represents pairwise incompatibilities by a finite simple undirected graph. The proposed claim is that connectedness suffices to divide the vertices into two groups so every edge crosses between groups.

A triangle refutes the claim. Assign A to the first group and its neighbour B to the second. The third vertex C is adjacent to both, so neither group is available. The failure concerns the universal claim, not the ability to divide any graph: a four-vertex cycle A-B-C-D-A admits groups {A,C} and {B,D}.

Follow the failed operation. Along a path, successive vertices can alternate between the two groups. Returning around an odd cycle forces its final edge to join vertices assigned to the same group. That identifies an obstruction worth seeking.

The next question is: For a given finite simple undirected graph, can we construct the division or return an odd cycle that explains why it is impossible? The answer form now serves both allocation and diagnosis.

B.5:5.1 supplies the broader construction. Traverse each component by breadth-first search and assign groups by even or odd depth. If every edge joins opposite parities, the assignment works. An edge joining equal parities combines with the two parent paths up to their last shared vertex to give a simple odd cycle. The construction therefore answers the new question for the stated graph class.

The earlier connectedness requirement can be dropped: work through each component, including isolated vertices. For a real allocation, establish that the graph represents the relevant pairwise incompatibilities. Three-way constraints would change that application question.