0
$\begingroup$

Given a balanced bipartite graph with $2n$ vertices. Do we have any upper bound for the maximum number of edges such that the graph is planar (i.e., a bound that is stronger than $6n-6$)?

$\endgroup$
1
$\begingroup$

In any bipartite graph, we can improve the upper bound. Combine Euler's formula $V-E+F=2$ with the inequality $2E \ge 4F$ caused by each face having at least $4$ sides (since there are no odd cycles) and we get $E \le 2V-4$. That is, with $2n$ vertices, we have at most $4n-4$ edges.

We can't improve the bound if the graph must be balanced. The graph below achieves the maximum possible number of $4n-4$ edges, is a balanced bipartite graph, and we can extend it to have $2n$ vertices for any even $n$.

enter image description here

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.