Math 240 Discrete Mathematics - Intro to graph coloring

Assignment 5: Reccurence for dimes nickels pennies

9 cents can be written as a permutation of ::

5 1 1 1 1 1 5 1 1 1 1 1 5 1 1 1 1 1 5 1 1 1 1 1 5 1 1 1 1 1 1 1 1 1

where 5 is a coin of 5 cents and 1 is a coin of 1 cent

Planar Graphs

Prop: A (simple) planar graph $G=(V,E)$ satisfies $|E| \leq 3|V| - 6$

Recap: Add edges to $G$ until we can’t add more edges and still have a simple planar graph then we have $G^\prime = (V,E^\prime)$ which is a triangulation all faces are triangles.

Then $ 3 \cdot number\ of\ faces\ in\ G^\prime = 2 \cdot number\ of\ edges\ in\ G^\prime $ \[3|F^\prime| = 2 |E^\prime|\]

Since also $|V| + |E^\prime| = |F^\prime| + 2 $. we obtain $|E^\prime|=3|V|-6$. Since $E \subset E^\prime$, we get \[|E| \leq 3|V| - 6 \]

More generally, if $f\in F$ and $|f|$ is the number of sides of edges that are incident to $f$, then

$ \sum_{f\in F} |f| = 2 |E|$

Is Petersen graph planar?

.. image:: https://upload.wikimedia.org/wikipedia/commons/thumb/9/91/Petersen1\_tiny.svg/200px-Petersen1\_tiny.svg.png

It has 15 edges, $|E| = 15$ and 10 vertices, $|V| = 10$. but $3|V|-6 = 24 \not\geq 15$. Therefore Petersen graph is not planar.

.. image:: |filename|/math240res/images/200px-Petersen1_tiny.svg_circled.png

Identifying the circled pairs of vertices gives

$K_5$ (five vertices all edges btw vertices)

.. image:: https://upload.wikimedia.org/wikipedia/commons/thumb/c/cf/Complete\_graph\_K5.svg/245px-Complete\_graph\_K5.svg.png

Petersen planar $\leftrightarrow$ K5 planar.

$3|V| -6=9 |E| = 10$, so K5 not planar.

Prop: If $G$ simple, planar, all faces have length $\geq 4$ then \[|E| \leq 2 |V| -4 \]

Proof: $\sum_{f \in F} |f| = 2|E|$ .

Let $K_n =$ n vertices all edges

$K_{n,n} = $ “complete bipartite graph with n vertices on each side”

This means if $K_{3,3}$ is plnar then all faces have length $\geq 4$ so $|E| \leq 2|V| -4 $.

But $|E| = 9 , 2|V| -4 =8$ so $K_{3,3}$ not planar

Theorem

$G$ is non-planar if and only if we can “identify” connected groups of vertices in $G$ to get $K_{3,3}$ or $K_5$

Graph Colouring

Map

Q: how many colours needed to colour the map so that countries with common border receive different colour.

(4-colour Theorem): 4 colours suffice for any map.

Definition

Given a graph $G=(V,E)$, a proper k-colouring of $G$ is a function $f:V \to \{1,2,…k\}$ s.t. for all {u,v} in $E$, $f(u)\not= f(v)$. The chromatic number $\chi(G)$ is the smallest $k$ s.t. $G$ has a proper k-colouring.

Examples

$\chi(K_n) = n$

$\chi (K_{n,n}) = 2$

Proposition

Let $\triangle (G) = \max \{d(v):v \in V\}$ (that triangle means degree)

let $\omega (G) =$ largest $i$ such that $K_i$ is a subgraph of $G$.

Then $\omega (G) \leq \chi (G) \leq \triangle(G) +1$

Proof

$\omega (G) \leq \chi (G)$ Vertices of any clique must all receive diff colours.

$\chi (G) \leq \triangle (G) + 1$ “greedy colouring algorithm”