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

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)

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”