0
$\begingroup$

In one of the corollaries to Euler's connected planar graph theorem ($~v-e+f=2~$, where $~v~$ is the number of vertices, $~e~$ if the number of edges, and $~f~$ is the number of faces), the proof states that

Assume every vertex has degree $~6~$ or more. Then $~6v≤2e~$ since every vertex is the end of at least six edges.

My problem is that I don't really understand why $~6n≤2m~$. Could someone explain this in layman's terms? Thank you!

$\endgroup$

1 Answer 1

2
$\begingroup$

Every edge is incident to two vertices. So there are $2m$ vertex-edge pairs (here $m$ is evidently the number of edges.)

By assumption, each vertex is in at least 6 edges, so there are at least $6n$ vertex-edge pairs (where $n$ is the number of vertices); and possibly more, if some vertices have higher degree.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .