Adjacency graph of cutting plane is a bipartite graph 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


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...)
