Proof that bipartite planar graph has a vertex of degree at most 3

570 Views Asked by At

I'm trying to understand proof that bipartite planar graph has a vertex of degree at most 3.

I found this proof: Prove that a bipartite planar graph has a vertex of degree at most 3 .

However, I'm not sure where did the $4v$ come from at the end of the proof. Could you please explain that part?

Thanks

2

There are 2 best solutions below

0
On

If all vertices have degree at least $4$, then the sum of the degrees of the vertices is at least $4v$. We know from the handshaking lemma that the sum of the degrees of the vertices is $2e$, so $2e\ge 4v$ if each vertex has degree $4$ or more. But from $(*)$ we know that $2e\le 4v-8<4v$, so we have a contradiction, and therefore at least one vertex must have degree less than $4$.

0
On

They noted that $2e$ is the sum of the degrees of the vertices in the graph.

If each vertex has degree at least $4$, then the sum of degrees is at least $4v$. So $2e \ge 4v$.