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


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.
