4
$\begingroup$
  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.

$\endgroup$
  • 4
    $\begingroup$ It seems unlikely that they want you to prove the four-colour theorem... en.wikipedia.org/wiki/Four_color_theorem $\endgroup$ – Johanna Dec 17 '14 at 20:30
  • $\begingroup$ Sorry this was mentioned in my graph theory notes. Was trying to prove it for a few hours. Should have 'googled' it first. $\endgroup$ – George J. Adams Dec 17 '14 at 20:38
  • 2
    $\begingroup$ I recommend trying to prove the five and six colour versions though: they are nice excercies. If you are interested, the book "The Map Color Theorem" by Ringel is very good. $\endgroup$ – Johanna Dec 17 '14 at 20:39
  • $\begingroup$ Can you actually help me with the 5/6 colour version then. $\endgroup$ – George J. Adams Dec 17 '14 at 20:43
  • $\begingroup$ They basically follow from part 1 in your question: consider the maximum number of bordering regions if you know the maximum degree of each vertex. $\endgroup$ – Johanna Dec 17 '14 at 20:46
2
$\begingroup$

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?)

$\endgroup$
  • $\begingroup$ ^Is my method for the third claim correct? $\endgroup$ – George J. Adams Dec 17 '14 at 20:43
  • 1
    $\begingroup$ I'd say yes; it's essentially equivalent to the induction method. $\endgroup$ – Ilmari Karonen Dec 17 '14 at 20:43
  • $\begingroup$ Can you actually elaborate on the induction method. $\endgroup$ – George J. Adams Dec 17 '14 at 20:44
  • 1
    $\begingroup$ The simple inductive argument I originally thought of actually requires a non-trivial lemma (although I do still think your version is valid). That said, I added a quick inductive proof above that every tree (of two or more vertices) has at least two leaves. $\endgroup$ – Ilmari Karonen Dec 17 '14 at 21:09
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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$).

$\endgroup$

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.