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.
Here's an example