Monthly Archives: October 2012

Bipartite graphs

The topic of this post is bipartite graphs. These are graphs whose vertex set can be partitioned into two parts, called partite sets, such that all edges xy of the graph are such that x and y are in different partite sets. The most common examples of bipartite graphs are the trees and even cycles. Any union of bipartite graphs obviously yields another bipartite graph. The complete bipartite graph K_{m,n} consists of two partite sets X and Y containing m and n elements respectively with all possible edges between X and Y filled out.

To conclude here is a list of characterizations.

Suppose G is a graph with at least two vertices. The following are equivalent:

1. G is bipartite.

2. Every cycle of G is even.

3. \chi(G)=2.

1 \Leftrightarrow 2: Suppose G is bipartite and there is a cycle v_1v_2\cdots v_kv_1 which has an odd number of edges. Now v_i for odd i is in the same partite set as v_1. But since the cycle is odd v_1 and v_k are in the same partite set which is a contradiction.

Conversely suppose G has no odd cycles and x\in V(G). Let X=\{y\in V(G):d(x,y) is even \} and Y=\{y\in V(G):d(x,y) is odd \}. Then X and Y partition V(G). Suppose pq\in E(G) and p,q\in X. Neither p nor q is x for otherwise d(x,q) (resp d(x,p)) is odd. So it makes sense to talk of a path from x to p (resp q). Let x=v_0v_1\cdots v_{2k-1}v_{2k}=p and x=w_0w_1\cdots w_{2m-1}w_{2m}=q be the shortest such paths. (Note that they are necessarily even). Let the last common vertex in the two paths be v_i=w_i. Now the cycle v_iv_{i+1}\cdots v_{2k}w_{2m}w_{2m-1}\cdots w_{i+1}w_i=v_i is an odd cycle. This contradiction proves there are no edges within vertices of X. Similarly there are no edges within vertices of Y. The result follows.

1 \Leftrightarrow 3: This is more of a restatement of the definition of a bipartite graph then a characterization, since the two partite sets may be considered as differently colored subsets of V(G).\Box

In addition to the above general characterizations the following are also true:

a) G is bipartite iff the spectrum of G is symmetric with respect to the origin.

b) Suppose G is connected and \lambda is its maximum eigenvalue. Then G is bipartite iff -\lambda is an eigenvalue of G.

c) Suppose G is planar. Then G is bipartite iff b(R), the bound degree of a region R, is even for every region R.

I will defer a proof of these statements.


Leave a comment

Filed under Combinatorics, Graph theory