Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

This is a homework problem and my solution. To me I think I get the main ideas and understand what is going on but I need work on my proof writing I think as I don't get full credit when I think I should get a little better than what I have been getting.

$$\text{For $n \geq 2$, planar graphs with $n$ vertices have at least two vertices whose degree is at most 5.}$$

$Proof$: Let $G$ be a planar graph. We will do cases, $n=2$ then $n > 2$.

$Case1.$ For $n=2$, if $G$ is a planar graph with $n$ vertices then either $G$ is the complete graph of order $2$, $K_2$, or $G$ is the null-graph of order $2$, $N_2$. In the former case each vertex has degree 1 and in the latter case each vertex has degree 0 so the condition is satisfied.

$Case2.$ Suppose $n >2$. We will further assume that $G$ is connected. Then since $G$ is a planar graph, we have $$e \leq 3n -6$$ where $e$ is the number of edges of $G$.

Assume for contradiction that at most one vertex has degree smaller than or equal to 5.

Suppose there is only one such vertex, $v_k$ where $\mathrm{deg}(v_k)\leq 5$. Then by the handshaking lemma we have $$2e = \sum_{i=1}^n \mathrm{deg}(x_i) \geq 6(n-1) + \mathrm{deg}(v_k)$$ $$\Rightarrow \mathrm{deg}(v_k) \leq 2e-6n+6 \leq 2(3n-6)-6n+6=-6$$ a contradiction.

Suppose there are no such vertices, then all vertices has degree larger than or equal to 6.

Then,

$$2e = \sum_{i=1}^n \mathrm{deg}(x_i) \geq 6n \Rightarrow e \geq 3n$$ $$\Rightarrow 3n \leq e \leq 3n -6 $$ $$\Rightarrow 0 \leq -6$$ a contradiction.

Suppose that $G$ is disconnected and has connected components $G_1,G_2,...G_m$. If any of the connected components have $n \geq 2$ vertices, the condition is satisfied by above. The other case is they all only have $1$ vertice in which case $G$ is just a null graph and the condition is satisfied.


This is really more of a draft but it has all my ideas.

Thank you very much if you took the time to read this.

share|improve this question
    
I assume that the proof is fine since no one has said anything. Honestly I think it is good, I just thought I could type this up to see if I have some perverse view on something. –  Starlight Dec 7 '12 at 3:16
1  
Your reasoning looks fine. –  Andrew Uzzell Dec 8 '12 at 18:07
    
Ok sounds good thank you. –  Starlight Dec 9 '12 at 11:10
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.