Proof on Graph Theory.

Question

1. If G is a connected planar graph, then G has a vertex of degree at most 5.
2. Any planar graph can be colored with 5/6 colors.
3. Any tree has atleast one leaf.

Solutions: Although I've read a lot on this topic I'm totally stumped at the first two. (Please help!)

My reasoning for the third one is as follows: Start from any vertex in the tree and start drawing edges connecting each vertex to every other vertex. (If no leaf then each vertex needs to have degree greater or equal to 2.) If we try to make each vertex have degree two we will reach a point where we have no vertices left and if we try to make an edge between any two used vertices we'll make a cycle.

Answer 1

The first claim can be proved using Euler's formula: for a finite, connected planar graph with $v$ vertices, $e$ edges and $f$ faces, $v - e + f = 2$.

The second claim is the well-known four-color theorem. As noted by Johanna in the comments, it seems unlikely that you would be asked to prove this as an exercise.

The third claim can be proved by applying the fact that a tree with $n$ vertices has $n-1$ edges.

---

Ps. Alternatively, for the third claim, we can inductively prove the stronger claim that any tree with two or more vertices has at least two leaves.

Specifically, our induction assumption is that all trees with $v$ vertices, where $2 \le v \le n$, have at least two leaves. Clearly, this is vacuously true for $n=1$, so we can take that as our base case.

Now, consider a tree with $v = n+1$ vertices, and observe that deleting any edge of this tree leaves you with two smaller (but non-empty) trees. If one of these smaller trees has only one vertex, then it was a leaf in the original tree; otherwise, by the induction assumption, each of the smaller trees must have at least two leaves, and joining it to another tree with an edge can eliminate at most one of its leaves. Either way, the combined tree will inherit at least one leaf from each subtree, and thus has at least two leaves.

(Also note that this stronger claim is as strong as it can get: for any $n$, there exists an $n$-vertex tree with exactly two leaves. Exercise: what does such a tree look like?)

Answer 2

1) Suppose to the contrary that all vertices have degree at least $6$ and the graph $G$ is planar. By the Handshake Lemma, there are at least $3v$ edges. By a corollary to Euler's formula, we have $e \leq 3v - 6$, a contradiction. And so there must exist at least one vertex of degree at most $5$.

2) I will have to think more on this and will edit if necessary.

3) We prove a lemma. Any graph with $\delta(G) \geq 2$ (minimum degree of $2$) has a cycle. So by the Handshake Lemma, $\sum_{v \in V} d(v) \geq \sum_{v \in V} \delta(G) = 2V$, which implies there are at least $V$ edges in $G$.

By this lemma, we note that any graph with minimum degree $2$ cannot be a tree, as a tree has $V-1$ edges. Thus, there must be a leaf (a vertex with degree $1$).

Answer 3

Let $G$ be a simple, planar graph with $p$ vertices, $q$ edges, and $r$ regions.

For part one:

Let $r_n$ be the number of regions bounded by $n$ edges. Then

$$2q=r_1+2r_2+3r_3+\cdots+nr_n=3r_3+\cdots+nr_n\geq3(r_1+r_2+\cdots r_n)=3r$$

since $G$ is simple (no loops or multiple edges means that $r_1=r_2=0$). So $r\leq 2q/3$. Now

$$2=p-q+r\leq p-q+2q/3=p-q/3$$ Thus

$$q\leq3p-6$$

If $N(G)$ gives the set of nodes in $G$, then

$$\sum_{v\in N(G)}\text{deg }v=2q\leq6p-12$$

So

$$\frac{\sum\text{deg }v}{p}\leq 6-\frac{12}{p}<6$$

Then there must exist a vertex in $G$ with at most degree $5$.

For part two:

You only have to argue that every subgraph of a simple, planar graph is simple and planar to complete the proof of part 2. Once you have established that fact a simple induction shows that every simple, planar graph is $5$-degenerate, that is it is at most $6$-colorable.