Showing inequality about number of vertices with ceratin degree for planar graphs

100 Views Asked by At

I am currently struggling on showing the following inequality for planar graphs without loops. Let $\delta(G) \geq 3$ and $\tau_i$ be the number of vertices with degree $i$, then: $$ \tau_5 + 2 \tau_4 + 3 \tau_3 \geq 12 + \tau_7 + 2 \tau_8 + 3 \tau_9 + \ldots + (\Delta-6) \tau_\Delta $$

So far I know that $\delta(G) \leq 5$ since the graph is planar and without loops. Furhtermore I tried using the inequality $3n-6 \geq m$ for planar graphs or counting the vertices in different ways however I am unable to introduce the scalars $(i-6) \tau_i$ into the equation.

I also tried proving this fact by induction over $\Delta$ however I got stuck at the induction step when trying to reduce it to the base case by merging vertices somehow.

Any tips/help would be greatly appreciated.

1

There are 1 best solutions below

1
On BEST ANSWER

Elaborating on the comments by Calvin Lin I was able to find the following solution:

With the handshaking lemma we get that: $$ 2m(G) = \sum_{v \in V(G)} d(v) $$ Furthermore we now surely have $$ \sum_{v \in V(G)} d(v) = \sum_{i=3} ^\Delta i \tau_i $$ since in the second sum also the degree of each vertex is counted once.

Furthermore we now have for planar graphs that: $$ 2(3n(G) -6) \geq 2m $$ Combining these two we get $$ -12 \geq \sum_{i=3} ^\Delta (i-6) \tau_i $$ And with this $$ \tau_5 + 2 \tau_4 +3 \tau_3 \geq 12 + \sum_{i=7}^\Delta (i-6) \tau_i $$ Which was to be shown.