1
$\begingroup$

Each time you draw a line on a plane, you are cutting it in half. Suppose you keep doing this without drawing a line parallel to a previous one. An adjacency graph can be constructed to represent this where each node represents an undivided portion of the plane, and edges exist between portions that share a boundary edge (as created by the lines).

I want to prove that the adjacency graph is bipartite regardless of what lines are drawn.

I know that a graph is bipartite if it is 2-colourable and this could be used to prove that the adjacency graph is 2-colourable but I'm stuck with proving how a graph is 2-colourable by induction.

Any help is appreciated!! Thanks.

EDIT

Here's an example 1

$\endgroup$
2
$\begingroup$

As Learner pointed out, the problem is equivalent to showing that there is no odd circuit in the graph. Roughly, the idea is that when you move from a region to an adjacent region, we are moving across one line, while remaining on the same side with respect to all other lines. So to reach back to the original region, we need to cross this line again, showing that all cycles must be of even degree.

To write it more formally, for each line, consider the two half-planes it created. Assign (arbitrarily) value $0$ to one of them and $1$ to the other. Now each region is uniquely determined by a sequence of bits $0,1$, one bit for each line. Also, observe that adjacent regions differ in exactly one bit (corresponding to the line separating them).

Now consider any cycle starting from a vertex $v$. As we saw above, after moving along an edge to a adjacent vertex, exactly one of the bits is flipped. So the parity of the sequence is toggled. It follows from this that if we start from $v$ and move along some edges and reach $v$ again, there must be even number of edges (as the parity must come back to original parity of $v$). Hence all cycles have even degree.

$\endgroup$
1
$\begingroup$

Theorem: A graph with atleast one edge is 2-chromatic if and only if it has no circuit of odd length.

Reference: Page 168 Theorem 8-2 in Graph Theory by narsingn Deo.

Your adjacency graph doesnt have any circuit with odd degree.

$\endgroup$
1
$\begingroup$

Motivated by learner's answer, it seems not difficult to construct an indutive proof based on the fact that a line cut a region it passed into two parts that there must be no odd circuits involved. Hence the graph is 2-colorable and must be bipartite(I cannot find a proof of this, actually...)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.