0
$\begingroup$

So, by an informal proof I can show this is true: i. e., by creating a connected planar graph with $6$ nodes with one node of degree $5$, and $5$ nodes of degree $1$. Then by adding edges to a node with currently degree $1$, I can increase that node to degree $5$, eventually there will be a point where I can no longer add any edges without breaking the condition of planarity. And will have remaining nodes with degree no more than $5$.

Is there a better way to approach this? Perhaps with Euler's Theorem which states that a planar graph will satisfy the following condition: $V - E + R = 2$, where $v$ is vertices; $e$ is edges; $r$ is regions and we know that sum of all vertex degrees is equivalent to $2E$.

$\endgroup$
  • 1
    $\begingroup$ Thanks I forgot I can utilize Kuratowski's theorem, the $K_5$ minor is good insight $\endgroup$ – Diante Apr 8 '17 at 0:44
  • 2
    $\begingroup$ I don't see obvious ways to get a $K_5$ minor here, and it's certainly not going to follow from all nodes having degree $5$: what about the icosahedron? Euler's formula is a better approach. $\endgroup$ – Misha Lavrov Apr 8 '17 at 0:58
2
$\begingroup$

Yes, Euler's formula is a good start. So, $n - m + f = 2$ for any connected non-trivial planar graph $G$, where $n$ is the number of vertices, $m$ is the number of edges and $f$ is the number of faces. If $G$ is a tree than it obviously has a leaf that is a vertex of degree $1$. If $G$ contains a cycle, then each edge belongs to at most $2$ faces, while each face contains at least $3$ edges, so $3f \le 2m$ that is $f \le \frac23 m$. Then $n - m + f + \frac23 m \ge 2 + f$, therefore $3n - 6 \ge m$.

Also by handshake lemma we have $\sum_{v \in V(G)} \deg v = 2m$. So if $\deg v \ge 6$ for all $v \in V(G)$, then $6n - 12 \ge 2m \ge 6n$. This contradiction shows that there is a vertex of degree at most $5$.

$\endgroup$
  • 1
    $\begingroup$ There's something funny about the way the problem is stated, with the modifier "loop-free". If the OP were assuming a simple graph, I'd have expected him to call it "a simple graph" or else just "a graph". To my way of thinking, the expression "loop-free graph" carries the implication that multiple edges are allowed. Of course, in that case it would hardly have been necessary to post the question here, since counterexamples are so easy to find. $\endgroup$ – bof Apr 8 '17 at 3:17
  • $\begingroup$ @bof, it is indeed a simple graph just how the question was worded stated it that way $\endgroup$ – Diante Apr 11 '17 at 3:22
  • 1
    $\begingroup$ @Diante If it's a simple graph why didn't you mention that in the question? $\endgroup$ – bof Apr 11 '17 at 3:23

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.