The two colorable graph theorem, also known as the bipartite graph theorem, is an important concept in graph theory and combinatorics. It states that any undirected graph whose vertices can be divided into two disjoint sets such that no two vertices within the same set are adjacent can be colored with just two colors. This property of being 2-colorable (or bipartite) has many applications in computer science, operations research, and other fields.
Graph theory is the study of graphs, which are mathematical structures used to model pairwise relations between objects. A graph consists of a set of vertices (also called nodes or points) which are connected by edges (also called links or lines). Graphs can model many real-world situations such as networks of communication, data organization, transportation, and social interactions.
One of the most basic properties of graphs is whether they are colorable with a certain number of colors. Graph coloring involves assigning colors to each vertex in the graph such that no two adjacent vertices share the same color. The chromatic number of a graph is the minimum number of colors needed to color the graph.
The two colorable graph theorem characterizes a large class of graphs that can be colored with just two colors. Specifically, it says that a graph is 2-colorable if its vertices can be partitioned into two independent sets. The theorem was first proven by the mathematician Augustin Louis Cauchy in 1847.
Formal Statement of the Theorem
Let G = (V, E) be an undirected graph where V is the set of vertices and E is the set of edges. Then G is said to be bipartite if the vertices V can be partitioned into two disjoint sets V1 and V2 such that every edge e in E connects a vertex in V1 to a vertex in V2. Equivalently, a graph is bipartite if it contains no odd-length cycles.
The formal statement of the two colorable graph theorem is:
Two Colorable Graph Theorem: A graph G is 2-colorable if and only if it is bipartite.
This means that the vertices of any bipartite graph can be colored with two colors such that adjacent vertices have different colors. Conversely, if a graph can be colored with two colors in this way, it must be bipartite.
Explanation
The two colorable graph theorem establishes a clear link between the chromatic number of a graph and its structure. Specifically, it characterizes bipartite graphs as exactly those graphs that require only 2 colors.
The sufficiency part of the proof is straightforward. If G is bipartite with the two independent vertex sets V1 and V2, then coloring every vertex in V1 with color A and every vertex in V2 with color B produces a valid 2-coloring of G. No two adjacent vertices will have the same color since vertices in the same set are nonadjacent.
The necessity part requires more work. Assume that G has a 2-coloring using colors A and B. Consider the set V1 of all vertices colored A and the set V2 of all vertices colored B. Since the coloring is valid, V1 and V2 must be independent sets. Any edge e in G must connect vertices in V1 and V2, otherwise e would connect two vertices of the same color, contradicting the validity of the coloring. Therefore, G is bipartite.
This elegant theorem provides a powerful tool for analyzing graphs. Determining whether a graph is 2-colorable is an important first step in investigating its structure and properties.
Examples
Here are some examples to build intuition about bipartite graphs and two colorability:
- Complete bipartite graphs: These graphs have vertices partitioned into two independent sets V1 and V2 such that each vertex in V1 is connected to every vertex in V2. For example, K3,2 is a complete bipartite graph with |V1| = 3 and |V2| = 2.
- Trees: All trees are bipartite. A recursive coloring scheme proves this by induction on the number of vertices.
- Cycles: Even cycles are bipartite while odd cycles are not. C4, for example, is 2-colorable but C3 is not.
- Planar grids: Grid graphs like rectangular lattices are bipartite since vertices can be colored in a checkerboard pattern.
On the other hand, some non-examples include:
- Cycle graphs Cn for odd n ≥ 3
- Complete graphs Kn for n ≥ 3
- Star graphs
- Wheel graphs Wn for odd n ≥ 3
Trying to color these graphs with 2 colors always results in adjacent vertices having the same color.
Applications
The two colorable graph theorem has many applications in theory and practice. Here are some examples:
Graph Coloring
The theorem provides an efficient way to test if a graph is 2-colorable and find such a coloring if it exists. This can be done in linear O(V+E) time using breadth-first or depth-first search to check bipartiteness and construct the color classes.
Scheduling
A schedule assignment problem can be modeled as a graph with vertices as tasks and edges representing conflicts between tasks. The goal is to assign each task a slot or resource. If the graph is bipartite, two slots/resources suffice.
Channel Assignment
In communications networks, channels can be modeled as graph vertices and potential interferences as edges. Bipartiteness indicates two channels are enough for interference-free assignment.
tiles
The theorem ensures tileable pattern designs exist for bipartite graphs. Artists can design 2-colorable periodic tilings using different tiles for each color class.
Magnetic Materials
In physics, bipartite lattices of magnetic dipoles always contain ferromagnetic ground states according to the Kotonuy-Luttinger theorem. The bipartite property allows for two-valued spin configurations.
Related Results
The two colorable graph theorem spawned many related extensions and generalizations in graph theory. Here are some other important results.
Konig’s Theorem
For a bipartite graph G with partite sets X and Y, the number of edges in a maximum matching equals the number of vertices in a minimum vertex cover. This establishes a duality between two important graph concepts.
Hall’s Marriage Theorem
A bipartite graph G has a perfect matching (one saturating all vertices) if and only if for any set S of vertices on one side, |S| ≤ |N(S)| where N(S) is the set of neighbors of S. This characterizes matchability.
Euler’s Formula for Planar Graphs
If a planar graph with V vertices, E edges, and F faces is bipartite, then V – E + F = 2. This is a specialized case of Euler’s formula.
Matrix Characterization
A graph G is bipartite if and only if its adjacency matrix can be decomposed into two diagonal matrices under simultaneous permutation of rows and columns. This reveals a numerical characterization.
Generalizations
The two colorable graph theorem can be extended in various ways:
- k-colorable graphs: Graphs whose vertices can be colored with k colors such that no two adjacent vertices share the same color.
- List colorings: Vertices are each assigned lists of permissible colors, and must be colored from their list.
- Directed graphs: Colorings of directed graphs with forward and backward arcs.
- Hypergraphs: Colorings of hypergraphs with hyperedges connecting any number of vertices.
- Weighted graphs: Graphs with weights or costs associated with colors.
Studying these more complex scenarios leads to many deep questions and active research on graph coloring.
Proof Techniques
There are various ways to prove the two colorable graph theorem. Here are some common techniques.
Induction
An inductive proof recursively colors smaller vertex sets, combining the sets to color the overall graph. This constructs the required bipartition.
Traversal Argument
Start with any vertex and use breadth-first or depth-first search to traverse the graph, flipping colors when you cross partition sets. This eventually colors the whole graph.
Max Flow/Min Cut
View vertices as nodes, color A as source, color B as sink. Max flow being equal to min cut (bipartite sets) establishes 2-colorability.
Invariants
Show inductively that no matter how the graph is partially colored, it’s always possible to complete to a valid 2-coloring while maintaining the invariant.
Variations
Here are some variations on the two colorable graph theorem and bipartite graphs:
Nearly Bipartite Graphs
Nearly bipartite graphs contain a small non-bipartite component, but are 2-colorable if you remove a small number of vertices or edges. They have applications in social networks and clustering.
Bipartite Dimension
The bipartite dimension of a graph G is the minimum number of edges whose removal makes G bipartite. Computing the bipartite dimension is NP-hard in general.
Bipartite Completion
The bipartite completion problem asks for the minimum number of edge additions to make a graph bipartite. This problem arises in clustering scenarios.
Bipartite Edge Frustration
For a non-bipartite graph G, the bipartite edge frustration finds the minimum number of edges whose deletion makes G bipartite. It measures closeness to bipartiteness.
History
The origins of bipartite graphs and two colorability reach back centuries:
- 1736 – Leonhard Euler solves the Seven Bridges of Konigsberg problem using an implicit bipartite graph.
- 1847 – Augustin Cauchy formally proves the theorem in his paper on graph colorability.
- 1912 – Landau characterizes bipartite graphs as having all even cycles.
- 1930s – bipartite matching is studied by Konig, Egervary, and others.
- 1958 – Claude Berge formulates the bipartite maximum matching problem.
- 1965 – Lova ́sz proves the min-max theorem characterizing maximum matchings.
The two colorable graph theorem helped establish graph theory as a major field and continues to be a focal point of research today.
Conclusion
The two colorable graph theorem is a fundamental result in graph theory, with elegant proofs and diverse applications. It characterizes bipartite graphs as exactly the class of graphs that are 2-colorable. Studying bipartite graphs and two colorings leads to many important insights and tools in mathematics and computer science.
While the theorem is simple to state, it has rich implications and has motivated the study of graph coloring, matchings, planarity, and network flows. Variations like k-colorability, hypergraphs, and nearly bipartite graphs also showcase the impact and generality of this basic result on 2-colorings. Overall, the two colorable graph theorem provides a beautiful example of how simple mathematical structures can capture complex real-world relationships.
