# Is there a bipartite analog of graph theory?

I would like to compile a list of questions about graphs that have a non-trivial analogs for bipartite graphs.

Let me give the following examples:

1. Cycle vs Even cycle. Most questions about cycles in graphs have analogs in even cycles for bipartite graphs. For instance, it is trivial to show that a bipartite graph on an odd number of vertices cannot have a Hamilton cycle. In such a case the bipartite analog of a Hamilton cycle is a cycle missing exactly one vertex.

2. Minimal Girth. For graphs, 3 is the minimal possible length of a cycle. For bipartite graphs, the analogous number is 4.

3. Triangular vs quadrangular embeddings. In topological graph theory, a triangular embedding of a simple graph determine its genus. For bipartite graphs, the analog is an embedding with quadrangles as faces.

• I think there are various interesting examples. I cannot think of them from the top of my head but I plan to return to it. Good question! (I didnt see the point of item 2 though.) – Gil Kalai Mar 8 '10 at 22:23

Some classical theorems involving complete graphs have analogues involving complete bipartite graphs. For example, the complete graph $K_n$ has $n^{n-2}$ spanning trees, while the complete bipartite graph $K_{m,n}$ has $n^{m-1} m^{n-1}$ spanning trees. Finding the largest complete subgraph of a graph is a standard NP-hard problem, and finding the largest (in terms of number of edges) complete bipartite subgraph of a bipartite graph is also an NP-hard problem.