Number of edges in planar bipartite graph.

Question

Suppose G=(V,E) is a planar bipartite graph such that $V_1$ and $V_2$ are the partite sets. Suppose for all $a \in V_1$, $deg(a)\le p$ and for all $b \in V_2$, $deg(b)\le q$. If $|V_1|=x$ and $|V_2|=y$, then can we deduce a bound for the number of edges in G in terms of p, q, x, and y?

Answer 1

Since each vertex in $ V_1 $ is connected to at most $ p $ vertices and $ V_1 $ has $ x $ vertices, the maximum number of edge connections from $ V_1 $ can be at most $ p \cdot x $. Similarly, for $ V_2 $, each vertex can connect to at most $ q $ vertices, leading to a maximum of $ q \cdot y $ connections originating from $ V_2 $. Thus, a straightforward upper bound on $ |E| $, considering only the degree constraints, is given by:

$ |E| \leq \min(p \cdot x, q \cdot y) $

According to Euler’s formula for planar graphs, if a graph has $ n $ vertices and $ m $ edges, then $ m \leq 3n - 6 $ for $ n \geq 3 $. However, since $ G $ is also bipartite and every face in a bipartite graph must have at least $4$ edges (due to the absence of odd cycles), the bound tightens to:

$ |E| \leq 2n - 4 $

where $ n = x + y $ (the total number of vertices in $ G $).

Considering both degree and planarity constraints:

$ |E| \leq \min(p \cdot x, q \cdot y, 2(x + y) - 4) $