If G is a connected, planar, bipartite graph with number of Edges >= 4,
then prove that (Number of Edges) <= 2(Number of Vertices) - 4
Can someone help me out? I'm just doing some practice problems and am sort of behind in this class. A step by step explanation of the proof and what i need to solve it would be greatly appreciated!
Edit: I tried this based on a property of Planar graphs
-For all planar graphs with >=4 edges, E <= 3v-6
-This implies 3V-6 <= 2V - 4
But this is obviously wrong. I feel like i might be in the right direction?
Use the second planarity theorem, which states $e \leq 2v - 4$ if there are no three-cycles in the graph. A cycle of length $3$ would contradict the bipartite property of the graph.
EDIT: You can prove the second planarity theorem quickly using the Euler planarity characteristic $v - e + f = 2$.
We know that, if there are no cycles of length $3$, every face must consist of at least four edges, and every edge must have two faces: $2e \geq 4f$. Hence, $2 - v = f - e\leq \frac{1}{2} e - e = -\frac{1}{2} e$
Note, since $2 - v \leq -\frac{1}{2} e$, we have $e \leq 2v - 4$.