MATH239

Professor: Kevin Hare | Term: Winter 2024

Download PDF

Github

Basic Principles

Combinatorics

The study of combinatorics is the study of counting things.

1. How many possible poker hands are there?
2. How many ways can we choose a 3 topping pizza with 10 toppings?
3. How many ways can we split 8 slices of pizza between 3 people?
4. How many ways can we make change for a dollar?

Notation

$A=\{a_1,a_2,...,a_n\}$ is an n-element set.

• All terms are different

• Order of terms does not matter, $\{1,2\}=\{2,1\}$

Example

Let $A$ be the set of primes less than 10, $A=\{2,3,5,7\}$.

Let $B$ be the set of odd numbers less than 10, $B=\{1,3,5,7,9\}$.

We denote the size of a set by $|A|$.

Example

From above, $|A|=4$, $|B|=5$.

Example

Choose a prime less than 10 and an odd number less than 10. I.e. $(2,1),(2,3),...,(7,9)$.

For this, we use the notation of $A\times B=\{(a,b):a\in A,b\in B\}$

We have $|A\times B|=|A|\cdot |B|$

In this case, $(A\times B)=4\cdot 5=20$

Example

Choose a prime less than 10 or choose an odd number less than 10.

Choices are 1,2,3,5,7,9. This is denoted by $A\cup B=\{x:x\in A$ or $x\in B\}$ (or $x$ is in both).

$|A\cup B|=6$

Example

Choose a number less than 10 that is prime and an odd number $\{3,5,7\}$

We denote this by $A\cap B=\{x:x\in A$ and $x\in B\}$

Fact

$|A\cup B|=|A|+|B|-|A\cap B|$

Definition

Let A be a set. We define a list of A as the set of elements of A where the order matters

Example

Let $A=\{2,3,5,7\}$ be the set of primes less than 10.

The possible lists of A include $(2,3,5,7)(3,2,5,7)(5,2,3,7)\dots (3,7,2,5)(7,5,3,2)$ In this case there are 24 lists of $A=\{2,3,5,7\}$

Note, all elements in A will occur exactly once in each list. That is, lists are length $|A|$.

Question

Let A be a set with $|A|=n$. How many lists of A are there?

Let $p_n$ be the number of lists of $A$ where $|A|=n$. We can partition the set of lists based upon the first element of the list.

There are $n$ choices for this first element. Let $x\in A$ be the first element of a list. The remainder of the list will be chosen from the list of $A\setminus \{x\}$.

Note that $|A\setminus \{x\}|=n-1$

Hence there are $p_{n-1}$ choices for the last $n-1$ elements of the list. As there were $n$ choices for $x$, we get $p_n=n\cdot p_{n-1}$.

Note $p_1=1$ (the only list from $\{x\}$ is $(x)$).

Hence $p_n=n\cdot p_{n-1}=n\cdot (n-1)\cdot p_{n-2}\dots =n(n-1)\dots (2)p_1=n!$

Theorem

Let $A$ be a set with $|A|=n$. Then the number of lists of $A$ is $n!$

Definition

A subset of a set is a collection of elements from $A$ without repetition. Note a subset may be empty, or all of $A$. Order does not matter.

Example

Let $A=\{2,3,5,7\}$. The set of all subsets includes

$\{\},\{2\},\{3\},\{5\},\{7\},\{2,3\},\{2,5\},\{2,7\}...16$

We see that for each $x\in A$ a subset either contains $x$, or doesn’t contain $x$. This gives us two choices for all $x\in A$. Either it is in the subset or it is not.

This allows us to observe that the number of subsets of $A$ where $|A|=n$, is $2^n$.

Theorem

The number of subsets of $A$ with $|A|=n$, is $2^n$ (include or not; 2 options $n$ times).

Definition

Let $A$ be a set of size $n$. A partial list of size $k$ is an ordered list $(a_1,a_2,\dots ,a_k)$ with $a_i\in A$ and no repeats.

Example

Let $A=\{2,3,5,7\}$. Let $k=2$. The partial lists of length $2$ of $A$ are

(2,3),(3,2),(2,5),(5,2)

(2,7),(7,2),(3,5),(5,3)

(3,7),(7,3),(5,7),(7,5)

Question

For every $n$ and $k$, how many partial lists of length $k$ are there of $\{1,2,\dots ,n\}$

Notice

In the previous example, there are $4$ choices for the first element of the list. After we have chosen the first element, we have only 3 choices for the second. After, we are done.

This gives us the number of partial lists is $4\cdot 3=12$

In general, for $|A|=n$, and $k\le n$, we have

1. $n$ choices or the first element

2. $n-1$ choices or the second

k. $n-k-1$ choices for the $k^{th}$ element

this gives $\dots$

Theorem

The number of partial lists of length $k$ of $\{1,2,\dots ,n\}$ is

$$n(n-1)(n-2)...(n-k+1)=\frac{n(n-1)(n-2)...(n-k+1)(n-k)...(2)(1)}{(n-k)(n-k-1)..(2)(1)}=\frac{n!}{(n-k)!}$$

Example

Find all of the subsets of size $2$ of $\{2,3,5,7\}$

$\{2,3\},\{2,5\},\{2,7\},\{3,5\},\{3,7\},\{5,7\}$

For every subset of length $k$ there are $k!$ orderings of the elements to get a partial list of length $k$. This is true for every subset.

This gives us that (# of subsets of size $k$ of $\{1,2,\dots ,n\}$) $\cdot k!=$ # of partial lists of length $k$ of $\{1,2,\dots ,n\}$

Theorem

Let $A$ be a set $|A|=n$, and $k\le n$. Then the number of subsets of subsets of size $k$ is

$$\frac{n!}{(n-k)!k!}=\left(\genfrac{}{}{0ex}{}{n}{k}\right)=\frac{\text{number of partial lists}}{k!}=\text{number of subsets}$$

See STAT230 for more on permutations and sets.

Meaning vs Algebra

There are many examples in combinatorics where we can manipulate the algebra to get a result or relationship.

This will tell you that something is true, but not why it is true.

We wish to find relationships between things we know how to count and things we want to count.

Example

Show $\left(\genfrac{}{}{0ex}{}{n}{k}\right)=\left(\genfrac{}{}{0ex}{}{n}{n-k}\right)$

We see that $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$ is the number of subsets of size $k$ of $\{1,2,\dots ,n\}$.

Let $S=\{a_1,a_2,\dots ,a_k\}$ be a subset of size $k$ of $\{1,\dots ,n\}$.

Notice

$S^{\prime }=\{1,2,\dots ,n\}\setminus S$ is a subset of size $n-k$.

(I.e if $n=10$, $A=\{2,3,5,7\}$ then $A^c=\{1,4,6,8,9,10\}$).

We see every $A$, a subset of size $k$ corresponds to a unique $A^c$, a subset of size $n-k$. Further every subset of size $n-k$ can be constructed in this way.

This tells us that the number of subsets of size $k$ is the same as the number of subsets of size $n-k$.

Bijections

Definition

Let $A$ and $B$ be sets.

1. A map $f:A\to B$ is said to be surjective (onto) if $\forall b\in B$ there exists (at least one) $a\in A$ with $f(a)=b$ (all $b$‘s are covered).

Example $f:\{1,2,3,4\}\to \{1,2\}$ by $f(1)=1,f(2)=f(3)=f(4)=2$

2. A map $f:A\to B$ is said to be injective if every $a\in A$ maps to a unique $b\in B$ (Sometimes called one-to-one).

Example $f:\{1,2\}\to \{1,2,3,4\}$ by $f(1)=2,f(2)=4$

3. A map $f:A\to B$ is called bijective (or one-to-one & onto) if it is both surjective and injective.

Example $f:\{1,2,3\}\to \{2,3,5\}$ by $f(1)=2,f(2)=3,f(3)=5$

Note, bijections can be reversed.

See

$f^{-1}(2)=1$ $f^{-1}(3)=2$ $f^{-1}(5)=3$

Observation

1. If there is a surjection $f:A\to B$, then $|A|\ge |B|$

2. If there is an injection $f:A\to B$, then $|A|\le |B|$

3. If there is a bijection $f:A\to B$, then $|A|=|B|$

Notation If there is a bijection $f:A\to B$, we say $A\leftrightharpoons$ B.

Example

Show $\left(\genfrac{}{}{0ex}{}{n}{k}\right)=\left(\genfrac{}{}{0ex}{}{n-1}{k-1}\right)+\left(\genfrac{}{}{0ex}{}{n-1}{k}\right)$Let $B(n,k)$ be the set of subsets of $\{1,\dots ,n\}$ of size $k$.

Notice

$$\begin{array}{rl}|B(n,k)|& =\left(\genfrac{}{}{0ex}{}{n}{k}\right)\\ |B(n-1,k-1)|& =\left(\genfrac{}{}{0ex}{}{n-1}{k-1}\right)\\ |B(n-1,k-1)|& =\left(\genfrac{}{}{0ex}{}{n-1}{k}\right)\end{array}$$

Example

$B(3,2)=\{\{1,2\},\{1,3\},\{2,3\}\}$ all subsets of size $2$ of numbers from $1-3$.

Our goal is to get a bijection from $B(n,k)$ to $B(n-1,k-1)\cup B(n-1,k)$

Notice $B(n-1,k-1)$ and $B(n-1,k)$ are disjoint (since they have different sizes). This gives,

$|B(n-1,k-1)\cup B(n-1,k)|=|B(n-1,k-1)|+|B(n-1,k)|$

We will construct a map $f$ with

$f:B(n,k)\to B(n-1,k-1)\cup B(n-1,k)$ by

$f(\{a_1,a_2,\dots ,a_k\})=\{a_1,\dots ,a_k\}\setminus \{n\}$

If $n\notin \{a_1,a_2,\dots ,a_k\}$ we see $f(\{a_1,\dots ,a_k\})=\{a_1,\dots ,a_k\}\in B(n-1,k)$

If $n\in \{a_1,a_2,\dots ,a_k\}$ then $f(\{a_1,\dots ,a_k\})$ is size $k-1$ and uses numbers $\{1,\dots ,n-1\}$.

This gives $f(\{a_1,\dots ,a_k\})\in B(n-1,k-1)$

Question: Is this a bijection?

Notice if $n\notin \{a_1,\dots ,a_k\}$ this map is injective and surjective. The inverse map is $f^{-1}(\{a_1,\dots ,a_k\})=\{a_1,\dots ,a_k\}$.

If $n\in \{a_1,\dots ,a_k\}$, say

$\{a_1,\dots ,a_k\}=\{a_1,\dots ,a_{k-1},n\}$ and $f^{-1}(\{a_1,\dots ,a_{k-1},n\})=\{a_1,\dots ,a_{k-1}\}\cup \{n\}$

This gives us that $f$ is a bijection. Hence

$|B(n,k)|=|B(n-1,k)|+|B(n-1,k-1)|$

$⟹\left(\genfrac{}{}{0ex}{}{n}{k}\right)=\left(\genfrac{}{}{0ex}{}{n-1}{k}\right)+\left(\genfrac{}{}{0ex}{}{n-1}{k-1}\right)$ as required.

Definition

Let $n\ge 0$, and $t\ge 1$. A multiset of size $n$ with $t$ types is a list $(a_1,\dots ,a_t)$ where $a_1+\dots +a_t=n$

Example

A person has $10$ pets, (fish, cats, and dogs)

Here $n=10,t=3$. We can have the list $(7,2,1)$.

We could have $t=4$ types (last type being birds). Then we have $(7,2,1,0)$ fish, cats, dogs, and birds respectively.

Theorem

The number of multisets of $n$ with $t$ types is

$$\left(\genfrac{}{}{0ex}{}{n+t-1}{t-1}\right)$$

Proof

We will do this by a bijective method. Let $A$ be the set of subsets of size $t-1$ of $\{1,\dots ,n+t-1\}$.

Clearly $|A|=\left(\genfrac{}{}{0ex}{}{n+t-1}{t-1}\right)$

Let $B$ be our set of multisets of size $n$ with $t$ types.

For example, we could have $n=10,t=4$.

Consider the subject $A$ given by

$\circ \circ \circ \circ \circ \circ \circ \bullet \circ \circ \bullet \circ \bullet$

Here there are $13=n+t-1$ circles, of which $3=t-1$ are erased off.

$\underset{\text{7 fish}}{\underbrace{(\circ \circ \circ \circ \circ \circ \circ )}}\bullet \underset{\text{2 cats}}{\underbrace{(\circ \circ )}}\bullet \underset{\text{1 dog}}{\underbrace{(\circ )}}\bullet \underset{\text{0 birds}}{\underbrace{}}$

This (admittedly non-rigorously defined) map is a bijection from $A$ to $B$.

This gives us $|A|=|B|$

$$\text{\hspace{1em}■}$$

Generating Series

Formal Power Series

In Math138 we considered power series/Taylor series, etc. Key difference in Math239 is we don’t care about convergence.

What we care about are the coefficients and the information they carry.

Definition

A formal power series $A(x)={\sum }_{n=0}^{\infty }{a}_n{x}^n=a_0+a_{1}x+a_2{x}^2+\dots$

Note: Often the $a_n$ are positive integers, and typically represent the size of some set we are interested in.

Example: Let $a_n$ be the number of lists of $\{1,2,\dots ,n\}$. In this case $a_n=n!$

We create the power series

$$A(x)=\sum _{n=0}^{\infty }{a}_n{x}^n=\sum _{n=0}^{\infty }n!x^n=1+x+2x^2+6x^3$$

Note: This only converges at $x=0$. We don’t care.

We can (and do) add and multiply formal power series in the obvious way.

Example

$$\sum _{n=0}^{\infty }{a}_n{x}^n+\sum _{n=0}^{\infty }{b}_n{x}^n=\sum _{n=0}^{\infty }(a_n+b_n)x^n$$

Example

$$\begin{array}{rl}(\sum _{n=0}^{\infty }{a}_n{x}^n)(\sum _{n=0}^{\infty }{b}_n{x}^n)& =(a_0+a_{1}x+a_2{x}^2+\dots )\cdot (b_0+b_{1}x+b_2{x}^2+\dots )\\ & =a_0{b}_o+(a_0{b}_1+a_1{b}_0)x+(a_0{b}_2+a_1{b}_1+a_2{b}_0)x^2\\ & =\sum _{n=0}^{\infty }(\sum _{k=0}^n{a}_k{b}_{n-k})x^n\end{array}$$

Note

We often call $x$ an indeterminate, not a variable. A variable is a placeholder that we occasionally evaluate at. We (almost never) evaluate at $x$. Hence we call it an indeterminate.

We often manipulate formal power series algebraically disregarding convergences.

Example

Let $A(x)={\sum }_{n=0}^{\infty }{x}^n=1+x+x^2+\dots$

Notice $x\cdot A(x)=x+x^2+x^3+\dots$

This gives $A(x)-xA(x)=1+0x+0x^2+0x^3+\dots =1$

Or equivalently,

$(1-x)(A(x))=1$

Or

$$\begin{array}{rl}A(x)& =\frac{1}{1-x}\leftarrow \text{(not a formal power series)}\\ (1-x)& =\frac{1}{A(x)}\leftarrow \text{(not a formal power series)}\end{array}$$

Theorem

Let $n\ge 0$ be fixed. Let $a_k$ be the number of subsets of $\{1,2,\dots ,n\}$ of size $k$.

Show

$$\begin{array}{r}\sum _{k=0}^{\infty }{a}_k{x}^k=\sum _{k=0}^n{a}_k{x}^k=\sum _{k=0}^{\infty }\left(\genfrac{}{}{0ex}{}{n}{k}\right)x^k=(1+x{)}^n\end{array}$$

Note if $k>n$, then $a_k=0$. Hence the first equality (everything after $n$ is 0)

Second equality comes from previous work $(a_k=(\genfrac{}{}{0ex}{}{n}{k}))$

Let $P(n)$ be the set of all subsets of $\{1,2,\dots ,n\}$

Let $B=$ set of all $(b_1,\dots ,b_n)$ with $b_i\in \{0,1\}$

Let $f(\{c_1,\dots ,c_k\})=(b_1,\dots ,b_n)$ where

$$b_i=\{\begin{array}{ll}1& \text{if }i\in \{c_1,\dots ,c_k\}\\ 0& \text{if }i\notin \{c_1,\dots ,c_k\}\end{array}$$

Let $n=10$

$f(\{1,2,5,7\})=(\underset{1}{\underbrace{1}},\underset{2}{\underbrace{1}},0,0,\underset{5}{\underbrace{1}},0,\underset{7}{\underbrace{1}},0,0,0)$

We see $f^{-1}((b_1,\dots ,b_n))=\{i:b_1=1\}$ $f^{-1}((0,1,1,0,1))=\{2,3,5\}$

We have

$$\begin{array}{rl}\sum _{k=0}^n{a}_k{x}^k=\sum _{k=0}^n\sum _{\{c_1,\dots ,c_k\}}{x}^k& =\sum _{k=0}^n\sum _{(b_1,\dots ,b_n){\sum }_{b_i}=k}{x}^{b_1+\dots +b_k}\\ & =\sum _{(b_1,\dots ,b_n)\in B}{x}^{b_1+\dots +b_n}\\ & =\sum _{b_1\in \{0,1\}{b}_2\in \{0,1\}{b}_n\in \{0,1\}}{x}^{b_1+\dots +b_n}\\ & =\sum _{b_1\in \{0,1\}}\sum _{b_2\in \{0,1\}}\dots \sum _{b_n\in \{0,1\}}{x}^{b_1+\dots +b_n}\\ & =\sum _{b_1\in \{0,1\}}\sum _{b_2\in \{0,1\}}\dots \sum _{b_n\in \{0,1\}}{x}^{b_1+\dots +b_n}\\ & =\sum _{b_1\in \{0,1\}}{x}^{b_1}\sum _{b_2\in \{0,1\}}{x}^{b_2}\dots \sum _{b_n\in \{0,1\}}{x}^{b_n}\\ & =(1+x)(1+x)\dots (1+x)\\ & =(1+x{)}^n\end{array}$$

Example

Show

$$\begin{array}{r}\left(\genfrac{}{}{0ex}{}{m+n}{k}\right)=\sum _{j=0}^k\left(\genfrac{}{}{0ex}{}{m}{j}\right)\left(\genfrac{}{}{0ex}{}{n}{k-j}\right)\end{array}$$

Notice $(1+x{)}^{m+n}={\sum }_{k=0}^{m+n}(\genfrac{}{}{0ex}{}{m+n}{k})x^k$

Further,

$$\begin{array}{rl}(1+x{)}^{m+n}& =(1+x{)}^m(1+x{)}^n\\ & =(\sum _{j=0}^m(\genfrac{}{}{0ex}{}{m}{j})x^j)(\sum _{i=0}^n(\genfrac{}{}{0ex}{}{n}{i})x^i)\end{array}$$

This gives us

$$\begin{array}{rl}(1+x{)}^{m+n}& =\sum _{j=0}^m\sum _{i=0}^n\left(\genfrac{}{}{0ex}{}{m}{j}\right)\left(\genfrac{}{}{0ex}{}{n}{i}\right)x^{j+1}\\ & =\sum _{k=0}^{m+n}\sum _{i+j=k}\left(\genfrac{}{}{0ex}{}{m}{j}\right)\left(\genfrac{}{}{0ex}{}{n}{i}\right)x^{j+i}\\ & =\sum _{k=0}^{m+n}\sum _{i+j=k}\left(\genfrac{}{}{0ex}{}{m}{j}\right)\left(\genfrac{}{}{0ex}{}{n}{k-j}\right)x^k\\ & =\sum _{k=0}^{m+n}\sum _{j=0}^k\left(\genfrac{}{}{0ex}{}{m}{j}\right)\left(\genfrac{}{}{0ex}{}{n}{k-j}\right)x^k\end{array}$$

By looking at the coefficient in front of $x^k$ we get that left hand side $=$ right hand side.

Notation, $[x^k]({\sum }_{}^{}{a}_k{x}^k)=a_k=$ coefficient in front of $x^a$.

Generating Series

Let $g_1,g_2,\dots$ be a sequence of numbers that we care about and encode some information.

Example

$g_n=\#$ of binary strings of length $n$

$g_n=\#$ of partial lists of length $n$ of $\{1,2,\dots ,100\}$

Definition

We define the generating series as $G(x)={\sum }_{n=0}^{\infty }{g}_n{x}^n$

We often generate these series using a weight function.

Definition

Let $A$ be a set. We say $w$ is a weight function where $\omega :A\to \mathbb{N}$. We further require that $A_n={\omega }^{-1}(n)=\{a\in A:\omega (a)=n\}$ is a finite set $\forall n$.

Example

Let $A$ = the set of all binary strings of any length.

I.e. $A=\{ϵ,0,1,00,01,10,11,000,\dots \}$

Good choices for $\omega$

• The length of the string (in this case $|A_n|=2^n$)

Bad choice for $\omega$

• The number of $1$‘s in the string

I.e. $A=\{1,10,01,1000,1000,\dots \}$

Here $A_1$ is infinite.

Example

Let $A$ be the set of all subsets of $\{1,2,\dots ,10\}$

Define $\omega :A\to \mathbb{N}$ by $w(\{a_1,\dots ,a_k\})=|\{a_1,\dots ,a_k\}|=k$

$$\begin{array}{rl}{A}_0& ={\omega }^{-1}(0)=\{\{\}\}\\ A_1& ={\omega }^{-1}(1)=\{\{1\},\{2\},\dots ,\{10\}\}\\ ⋮& \\ A_{10}& ={\omega }^{-1}(10)=\{1,2,3,4,5,6,7,8,9,10\}\\ A_{11}& =\{\},A_n=\{\}\text{ for }n\ge 11\end{array}$$

Definition

We define the generating series for $A$ with respect to $\omega$ as ${\Phi }_A^{\omega }(x)={\sum }_{a\in A}^{}{x}^{\omega (a)}$

In this case,

$$\begin{array}{rl}{\Phi }_A^{\omega }(x)& =x^{\omega (\{\})}+x^{\omega (\{1\})}+x^{\omega (\{2\})}+\dots +x^{\omega \{1,2,\dots ,10\})}\\ & =x^0+\underset{10\text{ subsets of size }1}{\underbrace{x^1+\dots +x^1}}+\underset{10\text{ subsets of size }2}{\underbrace{x^2+\dots +x^2}}+\dots +x^{10}\\ & =x^0+\left(\genfrac{}{}{0ex}{}{10}{1}\right)x+\left(\genfrac{}{}{0ex}{}{10}{2}\right)x^2+\dots +\left(\genfrac{}{}{0ex}{}{10}{9}\right)x^9+\left(\genfrac{}{}{0ex}{}{10}{10}\right)x^{10}\\ & =\sum _{n=0}^{10}|A_n|x^n\\ & =\sum _{n=0}^{\infty }|A_n|x^n\\ & =\sum _{n=0}^{10}\left(\genfrac{}{}{0ex}{}{10}{n}\right)x^n\end{array}$$

Note $|A_n|=\#$ of subsets of size $n$ taken from $\{1,\dots ,10\}=\left(\genfrac{}{}{0ex}{}{10}{n}\right)$

Theorem

Let $A$ be a set and $\omega$ a weight function. Then

$$\begin{array}{rl}{\Phi }_A^{\omega }(x)& =\sum _{a\in A}{x}^{\omega (a)}=\sum _{n=0}^{\infty }|A_n|x^n\end{array}$$

$$\begin{array}{rl}\sum _{a\in A}{x}^{\omega (a)}& =\sum _{a\in A_0\cup A_1\cup A_2\dots }{x}^{\omega (a)}\\ & =\sum _{n=0}^{\infty }\sum _{a\in A_n}{x}^{\omega (a)}\\ & =\sum _{n=0}^{\infty }\sum _{a\in A_n}{x}^n\\ & =\sum _{n=0}^{\infty }\sum _{a\in A_n}1\\ & =\sum _{n=0}^{\infty }{x}^n|A_n|\\ & =\sum _{n=0}^{\infty }|A_n|x^n\text{ as required.}\end{array}$$

Theorem

Let $g_n=\#$ of multisets of $n$ with $t$ types $=\left(\genfrac{}{}{0ex}{}{n+t-1}{t-1}\right)$

Use generating series to show

$$\begin{array}{r}\sum _{n=0}^{\infty }{g}_n{x}^n=\sum _{n=0}^{\infty }\left(\genfrac{}{}{0ex}{}{n+t-1}{t-1}\right)x^n=\frac{1}{(1-x{)}^t}\end{array}$$

Question

What is $A$ and what is $\omega$?

We want $A_n$ to be all the multisets of $n$ with $t$ types.

That is

$A_n=\{(a_1,\dots ,a_t):a_1+a_2+\dots +a_t=n\}$

We can define $w((a_1,\dots ,a_k))=a_1+\dots +a_t$

We can use

$$\begin{array}{rl}A& =\{(a_1,\dots ,a_t):a_1,\dots ,a_t\in \mathbb{N}\}\\ & =\underset{t\text{ times}}{\underbrace{\mathbb{N}\times \mathbb{N}\times \mathbb{N}\times \dots \times \mathbb{N}}}\\ & ={\mathbb{N}}^t\end{array}$$

This gives

$$\begin{array}{rl}\sum \left(\genfrac{}{}{0ex}{}{n+t-1}{t-1}\right)x^n& =\sum _{a\in A}{x}^{\omega (a)}=\sum _{n=0}^{\infty }|A_n|x^n\\ \sum _{a\in A}{x}^{\omega (a)}& =\sum _{(a_1,\dots ,a_t)\in A}{x}^{a_1+\dots a_t}\\ & =\sum _{a_1=0\dots \infty a_2=0\dots \infty a_t=0\dots \infty }{x}^{a_1}{x}^{a_2}\dots x^{a_t}\\ & =(\sum _{a_1=0}^{\infty }{x}^{a_1})(\sum _{a_2=0}^{\infty }{x}^{a_2})\dots (\sum _{a_t=0}^{\infty }{x}^{a_t})\\ & =(\frac{1}{1-x})(\frac{1}{1-x})\dots (\frac{1}{1-x})\\ & =(\frac{1}{1-x}{)}^t\end{array}$$

Recall from Math138 that

$\frac{1}{1-x}=1+x+x^2+x^3+\dots \forall |x|\le 1$

We don’t care about convergence.

We notice from this that

$1=(1-x)(1+x+x^2+\dots )$

Both $(1-x)$ and $(1+x+x{+}^2+\dots )$ are formal power series.

Definition

Let $A(x)$ and $B(x)$ be formal power series. If $A(x)B(x)=1$, then we say $A(x)$ is an inverse of $B(x)$ and similarly $B(x)$ is an inverse of $A(x)$.

Example

Let $A(x)=1-x-x^2$

Find $B(x)$ (if it exists) such that $A(x)B(x)=1$

Write $B(x)=b_0+b_{1}x+b_2{x}^2+b_3{x}^3+\dots$

This gives

$A(x)B(x)=(1-x-x^2)(b_0+b_{1}x+b_2{x}^2+\dots )=b_0+(b_1-b_0)x+(b_2-b_1-b_0)x^2+(b_3-b_2-b_1)x^3+\dots$

Notice $[x^0]1=1.[x^0]A(x)B(x)=b_0$. Hence $b_0=1$

$[x^1]1=$ coefficient in front $x^1$ of the power series $=0$.

$[x^1]A(x)B(x)=b_1-b_0=b_1-1$. Hence $b_1=1$

Next $[x^2]1=0$

$[x^2]A(x)B(x)=b_2-b_1-b_0$

Hence $b_2=2$

For general $n\ge 2$ we have.

$[x^n]1=0$

$[x^n]A(x)B(x)=b_n-b_{n-1}-b_{n-2}$

$⟹b_n=b_{n-1}+b_{n-2}$

Notice

$b_0=1,b_1=1,b_2=2,b_3=3,b_4=5,b_5=8,b_6=13,\dots$

This is the Fibonacci sequence.

I.e $(1-x-x)(1+x+2x^2+3x^3+5x^4+8x^5+\dots )=1$

We found the inverse.

Example

Show $A(x)=x+x^2$ does not have an inverse.

Assume it does, say

$B(x)=b_0+b_{1}x+b_2{x}^2+\dots$

As before we will consider $A(x)B(x)=1$, and match coefficients for $x^n$ for various $n$. I.e. consider

$[x^n]1=[x^n]A(x)B(x)$

For $n=0,[x^0]1=1$

$A(x)B(x)=b_{0}x+(b_1+b_0)x^2+(b_2+b_1)x^3+\dots$

For $n=0[x^0]A(x)B(x)=0$

Note $1\ne 0$, hence there are no solutions, and there is no inverse.

Theorem

Let $A(x)=a_0+a_{1}x+\dots$ be a formal power series. Then there exists an inverse $B(x)⟺a_0\ne 0$

Let $A(x)$ and $B(x)$ be formal power series. We define the composition as

$A(B(x))=a_0+a_{1}B(x)+a_{2}B(x{)}^2+\dots$ (assuming it exists)

Example

Let $A(x)=1+x+x^2+\dots$ Let $B(x)=x+x^2$

So

$$\begin{array}{rl}A(B(x))& =1+(x+x^2)+(x+x^2{)}^2+(x+x^2{)}^3+\dots \\ & =1+x+2x^2+3x^3+5x^4+8x^5+\dots \end{array}$$

Note: This series is the same as the inverse of $(1-x-x^2)$. Why?

Example

Let $A(x)$ be as before, $(1+x+x^2+x^3+\dots )$ and $B(x)=1+x$

$$\begin{array}{rl}A(B(x))& =1+(1+x)+(1+x{)}^2+(1+x{)}^3+\dots \\ & =\infty +\infty x+\infty x^2+\dots \leftarrow \text{Garbage}\end{array}$$

The composition is not well defined.

Theorem

Let $A(x)$ and $B(x)$ be formal power series. $B(x)=b_0+b_{1}x+b_2{x}^2+\dots$

If $b_0=0$ then $A(B(x))$ is well defined.

Proof

Assume $b_0=0$. We can write $B(x)=xC(x)$

$$\begin{array}{rl}\text{Hence }A(B(x))& =A(xC(x))\\ & =a_0+a_{1}xC(x)+a_2{x}^{2}C(x{)}^2+\dots \end{array}$$

Notice $[x^n]A(xC(x))=[x^n]{\sum }_{k=0}^n{a}_k{x}^{k}C(x{)}^k$

$$\text{\hspace{1em}■}$$

This sum is finite, hence all coefficients are finite.

Definition

We say that a power series $A(x)$ is rational if there exists polynomials $P(x)$ and $Q(x)$ such that$\frac{P(x)}{Q(x)}=A(x)$ or $P(x)=Q(x)A(x)$

Example

Let $A(x)=1+x+2x^2+3x^3+5x^4+8x^5$

Notice $A(x)=\frac{1}{1-x-x^2}$, hence $A(x)$ is rational.

Example

Let $A(x)=1+\frac{1}{2}x-\frac{1}{8}{x}^2+\frac{1}{16}{x}^3-\frac{5}{128}{x}^4+\dots$ such that $A(x)A(x)=1+x$

Exercise show $A(x)$ is not rational.

Sum Lemma

Let $A$ and $B$ be sets.

Let $A\cap B=\varnothing$ and $S=A\cup B$

Let $\omega$ be a weight function defined on $S$ (and hence $A$ and $B$)

Then

$$\begin{array}{r}{\Phi }_S^{\omega }(x)={\Phi }_A^{\omega }(x)+{\Phi }_B^{\omega }(x)\end{array}$$

Proof

$$\begin{array}{rl}{\Phi }_S^{\omega }(x)=\sum _{s\in S}{x}^{\omega (s)}& =\sum _{s\in A\cup B}{x}^{\omega (s)}\\ & =\sum _{s\in A\text{ or }s\in B}{x}^{\omega (s)}\\ & =\sum _{s\in A}{x}^{\omega (s)}+\sum _{s\in B}{x}^{\omega (s)}\\ & ={\Phi }_A^{\omega }(x)+{\Phi }_B^{\omega }(x)\end{array}$$ $$\text{\hspace{1em}■}$$

Note

$$\begin{array}{rl}{\Phi }_A^{\omega }& =\sum _{n=0}^{\infty }|A_n|x^b\\ & =\sum _{s\in S}{x}^{\omega (s)}\end{array}$$

here, $A_n={\omega }^{-1}(n)=\{s\in S:\omega (s)=n\}$

Example

Let $A$ be the subsets of $\{1,2,\dots ,n\}$ that contain $n$, and $B$ is all the subsets from $\{1,\dots ,n\}$ that do not contain $n$.

$A\cup B=\varnothing$

Further, $S=A\cup B$ is all the subsets of $\{1,\dots ,n\}$

Let $w(\{c_1,\dots ,c_k\})=|\{c_1,\dots ,c_k\}|$ be the size of the subset.

Then ${\Phi }_S^{\omega }(x)={\sum }_{s\in S}{x}^{\omega (s)}={\sum }_{k=0}^{\infty }|S_k|x^k$

Here $S_k$ is all subsets of $\{1,\dots ,n\}$ of size $k$.

Hence, $|S_k|=\left(\genfrac{}{}{0ex}{}{n}{k}\right)$

This gives ${\Phi }_S^{\omega }(x)={\sum }_{k=0}^{\infty }\left(\genfrac{}{}{0ex}{}{n}{k}\right)x^k={\sum }_{k=0}^n\left(\genfrac{}{}{0ex}{}{n}{k}\right)x^k$

$A=$ subsets of $\{1,\dots ,n\}$ that contain $n$.

$A_k=$ subsets of $\{1,\dots ,n\}$ that contain $n$ and are of size $k$.

There is a natural bijection from $A_n$ to $\widetilde{A_k}=$ subsets $\{1,\dots ,n-1\}$ of size $k-1$.

This is given by $\{c_1,c_2,\dots ,c_{k-1},n\}\to \{c_1,\dots ,c_{k-1}\}$

The inverse is $\{c_1,\dots ,c_{k-1}\}\to \{c_1,c_2,\dots ,c_{k-1},n\}$

This gives us

$$\begin{array}{rl}{\Phi }_A^{\omega }(x)=\sum _{k=0}^{\infty }|A_k|x^k& =\sum _{k=0}^{\infty }|\widetilde{A_k}|x^k\\ & =\sum _{k=0}^{\infty }\left(\genfrac{}{}{0ex}{}{n-1}{k-1}\right)x^k\end{array}$$

$B_m=$ the subsets of size $k$ from $\{1,\dots ,n\}$ that do not contain $n$. We can equivalently think of $B_m$ as the subsets of size $k$ from $\{1,\dots ,n-1\}$.

This gives ${\Phi }_B^{\omega }(x)={\sum }_{k=0}^{\infty }|B_k|x^k={\sum }_{k=0}^{\infty }\left(\genfrac{}{}{0ex}{}{n-1}{k}\right)x^k$

By the Sum Lemma, we have:

$$\begin{array}{rl}{\Phi }_S^{\omega }(x)& ={\Phi }_A^{\omega }(x)+{\Phi }_B^{\omega }(x)\text{ or}\\ \sum _{k=0}^{\infty }\left(\genfrac{}{}{0ex}{}{n}{k}\right)x^k& =\sum _{k=0}^{\infty }\left(\genfrac{}{}{0ex}{}{n-1}{k-1}\right)x^k+\sum _{k=0}^{\infty }\left(\genfrac{}{}{0ex}{}{n-1}{k}\right)x^k\end{array}$$

Considering $[x^k]$ of both sides we get: $\left(\genfrac{}{}{0ex}{}{n}{k}\right)=\left(\genfrac{}{}{0ex}{}{n-1}{k-1}\right)+\left(\genfrac{}{}{0ex}{}{n-1}{k}\right)$

Product Lemma

Theorem

Let $A$ be a set with weight function, $\omega$, and $B$ be a set with weight function $\upsilon$, we define: $S=A\times B=\{(a,b):a\in A,b\in B\}$

We define a weight function on $S$ as: $\mu (s)=\omega +\upsilon (s)=\omega \times \upsilon ((a,b))=\omega (a)+\upsilon (b)$

Then

$$\begin{array}{r}{\Phi }_S^{\mu }(x)={\Phi }_{A\times B}^{\omega \times \upsilon }(x)={\Phi }_A^{\omega }(x)\cdot {\Phi }_B^{\upsilon }(x)\end{array}$$

Proof

$$\begin{array}{rl}{\Phi }_S^{\sigma }(x)& =\sum _{s\in S}{x}^{\sigma (s)}\\ & =\sum _{(a,b)\in A\times B}{x}^{\omega (a)+\upsilon (b)}\\ & =\sum _{a\in A}\sum _{b\in B}{x}^{\omega (a)}{x}^{\upsilon (b)}\\ & =(\sum _{a\in A}{x}^{\omega (a)})(\sum _{b\in B}{x}^{\upsilon (b)})\\ & ={\Phi }_A^{\omega }(x)\cdot {\Phi }_B^{\upsilon }(x)\end{array}$$ $$\text{\hspace{1em}■}$$

Example

Let $A=\{1,2,3,4,5,6\}$ be the possibilities of a die. Let $\omega (a)=a$.

So ${\Phi }_A^{\omega }(x)=x+x^2+x^3+x^4+x^5+x^6$

Let $S=A\times A=\{(a,b):a,b\in A\}=\{(1,1),(1,2),\dots ,(2,1)\dots ,\}$

In this case:

$$\begin{array}{rl}{\Phi }_{A\times A}(x)& ={\Phi }_A(x)\cdot {\Phi }_A(x)\\ & =({\Phi }_A(x){)}^2\\ & =(x+x^2+x^3+x^4+x^5+x^6{)}^2\\ & =x^2+2x^3+3x^4+\underset{4\text{ ways to roll two dice such that their sum is equal to }5}{\underbrace{4x^5}}+5x^6+\dots \end{array}$$

Recall

Theorem

Let $A$ and $B$ be sets with weight $\omega$ and $\upsilon$. We define $A\times B=\{(a,b):a\in A,b\in B\}$ and $\omega \times \upsilon :A\times B\to N$ by $(\omega \times \upsilon )((a,b))=\omega (a)+\upsilon (b)$ Then ${\Phi }_{A\times B}^{\omega \times \upsilon }={\Phi }_A^{\omega }(x)\cdot {\Phi }_B^{\upsilon }(x)$

We can apply this theorem to higher products.

Infinite Sum Lemma

Notation

$A^k=\underset{k\text{ times}}{\underbrace{A\times \dots \times A}}=\{(a_1,\dots ,a_k):a_i\in A\}$

We similarly define

${\omega }^k=\underset{k\text{ times}}{\underbrace{\omega \times \dots \times \omega }}$, by

$({\omega }^k)(a_1,\dots ,a_k)=\omega (a_1)+\omega (a_2)+\dots +\omega (a_k)$

Define

$$\begin{array}{r}{A}^{\ast }=\bigcup _{k=0}^{\infty }{A}^k\end{array}$$

Example

Let $A=\{0,1\}$

$A^{\ast }=A^0\cup A^1\cup A^2\cup \dots$

$=\{(),(0),(1),(0,0),(0,1),(1,0),(1,1)\}$

We define ${\omega }^{\ast }:A^{\ast }\to \mathbb{N}$ by the property if $a\in A^k$ then ${\omega }^{\ast }(a)={\omega }^k(a)$

Example

Let $A=\{1,2\}$ and $\omega :A\to \mathbb{N}$ by $\omega (1)=1,\omega (2)=2$.

Then $(1,2,2,1,1)\in A^{\ast }$

$w^{\ast }((1,2,2,1,1))=w^5((1,2,2,1,1))=7$

There will be situations where ${\omega }^{\ast }$ is not a weight function. For example, if there exists $a\in A$ with $\omega (A)=0$.

Then ${\omega }^{\ast }(a)=0$, ${\omega }^{\ast }((a,a))=0+0=0$

${\omega }^{\ast }((a_1,\dots ,a_k))=0$

Hence $({\omega }^{\ast }{)}^{-1}(0)=\{ϵ,(a),(a,a),(a,a,a),\dots \}$

Theorem

Let $A$ be a set and $\omega :A\to \mathbb{N}$ a weight function such that $\omega (a)\ne 0,\forall a\in A$. Then,

$$\begin{array}{rl}{\Phi }_{A^{\ast }}^{{\omega }^{\ast }}(x)& =\frac{1}{1-{\Phi }_A^{\omega }(x)}\\ {\Phi }_{A^{\ast }}^{{\omega }^{\ast }}(x)& ={\Phi }_{{\bigcup }_{k=0}^{\infty }{A}^k}^{{\omega }^{\ast }}(x)\\ & =\sum _{k=0}^{\infty }{\Phi }_{A^k}^{{\omega }^{\ast }}(x)\\ & =\sum _{k=0}^{\infty }{\Phi }_{A^k}^{{\omega }^k}(x)\\ & =\sum _{k=0}^{\infty }({\Phi }_A^{\omega }(x){)}^k\\ & =\frac{1}{1-{\Phi }_A^k}\end{array}$$

Example

Let $A=\{1,2\}$ and $\omega :A\to \mathbb{N}$ as before with $\omega (1)=1$, $\omega (2)=2$.

$A^{\ast }=\{(),(1),(1,1),(1,2),(2,1),(2,2)\}$

$$\begin{array}{rl}{\Phi }_A^{\omega }(x)& =x^{\omega (1)}+x^{\omega (2)}=x^1+x^2\\ {\Phi }_{A^{\ast }}^{{\omega }^{\ast }}(x)& =\frac{1}{1-{\Phi }_A^{\omega }(x)}\\ & =\frac{1}{1-x-x^2}\\ & =1+x+2x^2+3x^3+5x^4+\dots \end{array}$$

We notice in this case that

$[x^4]{\Phi }_{A^{\ast }}^{{\omega }^{\ast }}(x)=5$

These correspond to

$(1,1,1,1),(1,1,2),(1,2,1),(2,1,1),(2,2)$

These are the $5$ lists in $A^{\ast }$ of any length using $1$ and $2$ that add to $4$.

Compositions

Definition

A composition is a list of positive integers. $(a_1,\dots ,a_k)$

The entries $a_i$ are the parts.

The length of a composition $(a_1,\dots ,a_k)$ is $k$.

The size is $|(a_1,\dots ,a_k)|=a_1+\dots +a_k$

Examples

The compositions of $4$ include

$(1,1,1,1),(2,1,1),(1,1,2),(1,2,1),(2,2)$ from the last example.

The last three examples are

$(1,3),(3,1),(4)$.

Let $\mathcal{C}$ be the set of all compositions. What is ${\Phi }_{\mathcal{C}}^{\text{size}}(x)$

We know that there are $8$ compositions of size $4$, for example.

Let ${\mathcal{C}}_1$ be all the compositions of length $1$. ${\mathcal{C}}_2$ of length $2$, etc.

Then

${\mathcal{C}}_1=\{(1),(2),(3),(4),\dots \}$

${\mathcal{C}}_2=\{(1,1),(1,2),(2,1),(2,2),(1,3),\dots \}$

We have ${\Phi }_{{\mathcal{C}}_1}^{\text{size}}=x+x^2+x^3=\frac{x}{1-x}$

We note that ${\mathcal{C}}_2={\mathcal{C}}_1\times {\mathcal{C}}_1$ and in general, ${\mathcal{C}}_k=({\mathcal{C}}_1{)}^k$

This allows us to write

$$\begin{array}{rl}{\Phi }_{\mathcal{C}}^{\text{size}}(x)& =\sum _{k=0}^{\infty }{\Phi }_{\mathcal{C}}^{\text{size}}\\ & =\sum _{k=0}^{\infty }({\Phi }_{{\mathcal{C}}_1}^{\text{size}}(x){)}^k\\ & =\frac{1}{1-{\Phi }_{{\mathcal{C}}_1}^{\text{size}}(x)}\\ & =\frac{1}{1-\frac{x}{1-x}}\\ & =\frac{1-x}{1-2x}\\ & =1+x^2+2x^2+4x^3+8x^4+\dots \end{array}$$

From this we conclude that the number of compositions of size k is,

$$\begin{array}{r}\{\begin{array}{l}{2}^{k-1}\text{ if }k\ge 1\\ 1\text{ if }k=0\end{array}\end{array}$$

Example

Let $g_n$ be the number of compositions of $n$ into $2$ or more parts using only the numbers $1,3,$ or $7$. Find an expression for ${\sum }_{n=0}^{\infty }{g}_n{x}^n$.

For example,

Weight $2\to (1,1)$

Weight $3\to (1,1,1)$

Weight $4\to (1,3),(3,1),(1,1,1,1)$

Let $A$ be the set $\{1,3,7\}.$ We will only be looking at $A^2,A^3,A^4,\dots$

We see ${\Phi }_A(x)=x^1+x^3+x^7$

The generating series we are interested in is

$$\begin{array}{rl}\sum _{n=2}^{\infty }{\Phi }_{A^n}(x)& =\sum _{n=2}^{\infty }({\Phi }_A(x){)}^2\end{array}$$

Note

$$\begin{array}{r}\sum _{n=2}^{\infty }{y}^n=y^2\sum _{n=0}^{\infty }{y}^n=\frac{y^2}{1-y}\end{array}$$

This allows us to find the generating series we want as

$$\begin{array}{r}\sum _{n=2}^{\infty }({\Phi }_A(x){)}^n=\frac{({\Phi }_A(x){)}^2}{1-{\Phi }_A(x)}=\frac{(x+x^3+x^7{)}^2}{1-x-x^3-x^7}\end{array}$$

Note

$$\begin{array}{rl}{\Phi }_A(x)& =\sum _{a\in A}{x}^{(\omega (a))}\\ & =\sum _{a\in \{1,3,7\}}{x}^{\omega (a)}\\ & =x^{\omega (1)}+x^{\omega (3)}+x^{\omega (7)}\\ & =x+x^3+x^7\end{array}$$

Example

Find the number of partitions of $n$, using only odd numbers, into an odd number of parts. Find the generating series.

Examples

$(1),(3),(5),(7)$

$(1,1,1),(1,1,3),(1,3,1),(3,1,1),(1,3,3)$

$(1,1,1,1,1)$

As before it is useful to determine the generating series into exactly $1$ part.

In this case, $A=\{1,3,5,7,\dots \}$

So

$$\begin{array}{r}{\Phi }_A(x)=\sum _{a\text{ odd}}{x}^{\omega (a)}=\sum _{a\text{ odd}}x+x^3+x^5+x^7+\dots \end{array}$$

Note

$$\begin{array}{rl}x+x^3+x^5+x^7+\dots & \\ & =x(1+x^2+x^4+x^6\dots )\\ & =x(1+(x^2{)}^1+(x^2{)}^2)+(x^2{)}^3)+\dots )\end{array}$$

This gives us that

$$\begin{array}{rl}{\Phi }_A(x)& =x+x^3+x^5\\ & =x(1+(x^2{)}^1+(x^2{)}^2+\dots )\\ & =\frac{x}{1-x^2}\end{array}$$

To find the generating series into an odd number of parts.

$$\begin{array}{rl}\sum _{n\text{ odd}}{\Phi }_{A^n}(x)& =\sum _{n\text{ odd}}({\Phi }_A(x){)}^n\\ & =\frac{{\Phi }_A(x)}{1-{\Phi }_A(x{)}^2}=\frac{\frac{x}{1-x^2}}{1-(\frac{x}{1-x^2}{)}^2}=\frac{x-x^3}{1-3x^4+x^4}\\ & =x+2x^3+5x^5+13x^7+34x^9+\dots \end{array}$$

This last step is just to double check you didn’t make a mistake. If any coefficients are negative, you made a mistake. If any of the small coefficients do not match up with an exhaustive set, you made a mistake.

From the series there should be $5$ compositions of $5$ into an odd number of odd parts.

$(1,1,1,1,1)$

$(1,1,3),(1,3,1),(3,1,1)$

$(5)$

Binary Strings

Define

A binary string is of the form $a_1,a_2,\dots ,a_n$ where $a_i\in \{0,1\}$

$(000,10110,100000001,\dots )$

The length of $a_1\dots a_n$ is $n$. We often use this as our weight function.

We use $ϵ$ to represent the empty string. (i.e. the string of length $0$).

If $A=\{0,1\}$ is the binary strings of length $1$, we use $A^2=\{00,01,10,11\}$

(This is the same as $\{(0,0),(0,1),(1,0),(1,1)\}$ from before but is easier to write).

As before

$\{0,1{\}}^{\ast }={\bigcup }_{k=0}^{\infty }\{0,1{\}}^k=$ set of all binary strings including $ϵ$.

Example Let $B$ be the set of all binary strings. Then

$$\begin{array}{rl}{\Phi }_B^{\text{length}}(x)& ={\Phi }_{\{0,1{\}}^{\ast }}^{\text{length}}(x)\\ & =\sum _{k=0}^{\infty }{\Phi }_{\{0,1{\}}^k}(x)\\ & =\sum _{k=0}^{\infty }({\Phi }_{\{0,1\}}(x){)}^k\end{array}$$

Here,

$$\begin{array}{r}{\Phi }_{\{0,1\}}^{\text{length}}(x)=x^{\text{length}(0)}+x^{\text{length}(1)}=x+x=2x\end{array}$$

This gives,

$$\begin{array}{r}{\Phi }_B^{\text{length}}(x)=\frac{1}{1-2x}=1+2x+4x^2+8x^3+16x^4+\dots \end{array}$$

Regular Expressions & Rational Languages

(Note: This is also discussed in CS360, CS365)

Definition

$ϵ,0,1$ are all regular expressions.

If $R$ and $S$ are regular expressions, then so is $R⌣S$. This can be read as “or”.

If $R$ and $S$ are regular expressions, then so is $RS$.

Example

$0,1$ are regular expressions. Hence $00$ is a regular expression as is $10$. Hence so is $00⌣11$. This represents the binary strings $\{00,10\}$.

Hence so is $(00⌣10)(00⌣10)$

This gives $\{0000,0010,1000,1010\}$ as the words represented.

If $R$ is a regular expression, so is $R^k$ for $k\ge 0$. This is $R^k=\underset{\text{k times}}{\underbrace{RR\dots R}}$

If $R$ is a regular expression, so is $R^{\ast }$

Here $R^{\ast }=\underset{\text{forever}}{\underbrace{ϵ⌣R^1⌣R^2⌣R^3⌣R^4⌣\dots }}$

Recall

Definition

Let $R$ and $S$ be regular expressions.

• $ϵ,0,1$ are regular expressions

• $R⌣S$ is a regular expression

• $RS$ is a regular expression

• $R^k=\underset{k}{\underbrace{RR\dots R}}$ is a regular expression

• $R^{\ast }=ϵ⌣R⌣R^2\dots$ is a regular expression

Example Consider $(0(00⌣11{)}^2{)}^{\ast }$

This is a regular expression, but what does it mean?

We see $ϵ$ is a word described by this regular expression

$\mathrm{0.00.00},\mathrm{0.00.11},\mathrm{0.11.00},\mathrm{0.11.11}$ are all words given by the regular expression $0(00⌣11{)}^2$, and hence given by this regular expression

Notice

$0(00⌣11{)}^2=0(00⌣11)(00⌣11)$

We also have $16$ words of length $10$ given by this expression. This comes from $(0(00⌣11{)}^2{)}^2$

Note $(0(00⌣11{)}^2{)}^2=0(00⌣11{)}^{2}0(00⌣11{)}^2=0(00⌣11)(00⌣11)0(00⌣11)(00⌣11)$

This includes

$\mathrm{0.00.00.0.00.00}$ $\mathrm{0.00.11.0.11.11}$ $\mathrm{0.11.00.0.11.0.0}$ etc.

There are $13$ more that are not listed.

Often for regular expressions, we wish to count the number of binary strings represented by this expression of a particular length.

In this case there is one word of length $0$, (namely $ϵ$)

There are $4$ words of length $5$

There are $4^2$ words of length $10$

In this case we can create a generating series $\sum a_n{x}^n$ where $a_n=\#$ of binary strings of length $n$ given by the regular expression.

We have in this case that

$$\begin{array}{rl}\sum _{n=0}^{\infty }& =1+4x^5+16x^{10}=4^3{x}^{15}+\dots \\ & =1+4x^5+(4x^5{)}^2+(4x^5{)}^3\\ & =\frac{1}{1-4x^5}\end{array}$$

Definition

Let $\mathcal{R}$ and $\mathcal{S}$ be sets of binary strings. We denote $\mathcal{R}\mathcal{S}=\{\alpha \beta :\alpha \in \mathcal{R},\beta \in \mathcal{S}\}$

Example

$\mathcal{R}=\{0,00,000,0000,\dots \}=$ all non-empty binary strings with only $0$

$\mathcal{S}=\{1,11,111\}$

$\mathcal{R}\mathcal{S}=\{01,011,0111,001,0011,0011,\dots \}$

$\mathcal{S}\mathcal{R}=\{10,110,1110,100,1100,11100,\dots \}$

$\mathcal{RR}=\{00,000,0000,\dots \}=R\setminus \{0\}$

$\mathcal{SS}=\{11,111,1111,11111,111111\}$

Definition

Let $R$ be a regular expression representing the words $\mathcal{R}$.

Let $S$ be a regular expression representing the binary strings $\mathcal{S}$.

The $ϵ,0,1$ are regular expressions representing the set $\{ϵ\},\{0\},\{1\}$ respectively.

Then $R⌣S$ is a regular expression representing the strings $\mathcal{R}\cup \mathcal{S}$.

Then $RS$ is a regular expression representing the strings $\mathcal{R}\mathcal{S}$.

Then $R^k=\underset{k}{\underbrace{R...R}}$ is a regular expression representing the language $\underset{k}{\underbrace{\mathcal{R}\dots \mathcal{R}}}=\{{\alpha }_1,\dots ,{\alpha }_k:{\alpha }_i\in \mathcal{R}\}={\mathcal{R}}^k$

$R^{\ast }=ϵ⌣R⌣R^2⌣R^3⌣\dots$ is a regular expression for the set of strings ${\mathcal{R}}^{\ast }=\{ϵ\}\cup \mathcal{R}\cup {\mathcal{R}}^2\cup {\mathcal{R}}^3\cup \dots ={\bigcup }_{k=0}^{\infty }{\mathcal{R}}^k$

Definition

Let $R$ be a regular expression. Then $\mathcal{R}$, the set of binary strings represented by $R$ is called a rational language (or a regular language).

Note

Not all subsets of binary strings are rational languages. For example, $\{0^n,1^n{\}}_{n=0}^{\infty }=\{ϵ,01,0011,000111,\dots \}$ is not a rational language.

Example

$\{0^p{\}}_{\text{p-prime}}=\{00,000,00000,\dots \}$ is not a rational language.

Example

Any finite set $\mathcal{R}$ is a rational language.

Ambiguous vs Unambiguous

Consider the two regular expressions.

$(1⌣11{)}^{\ast }$ and $1^{\ast }$. These both give the rational language $\{ϵ,1,11,111,1111,\dots \}$

We see that $(1⌣11{)}^{\ast }$ represents $111$ in three different ways. We have

$\mathrm{1.1.1}$ or $1.11$, $11.1$

We see $1^{\ast }$ has only one way to do this. Namely $\mathrm{1.1.1}$.

Ambiguous & Unambiguous Expressions

Definition

We say a regular expression is unambiguous if every string in the rational language is uniquely given by a unique representation. We say a regular expression is ambiguous if it is not ambiguous. Equivalently, there is at least one word in the language with at least two representations.

Example

$(1⌣0)(00⌣0)$

This is ambiguous. Notice

$00=0.0=ϵ.00$

Example

$1^{\ast }(00⌣0)$

We see that a word starts with some number of $1$s, that is described uniquely by $1^{\ast }$, and ends with $0$ or $00$, which again is unique.

This example is unambiguous.

Lemma

Let $R$ and $S$ be regular expressions which are unambiguous.

Let their rational languages be $\mathcal{R}$ and $\mathcal{S}$

Then $ϵ,0,1$ are all unambiguous

The regular expression $R\cup S$ is unambiguous if and only if $\mathcal{R}\cap \mathcal{S}=\varnothing$

The regular expression $RS$ is unambiguous if and only if there is a bijection from $\mathcal{R}\mathcal{S}$ to $\mathcal{R}\times \mathcal{S}$

I.e. for every $\alpha \in \mathcal{R}\mathcal{S}$, there is a unique $r\in \mathcal{R}$ and $s\in \mathcal{S}$ such that $\alpha =rs$

$R^{\ast }$ is unambiguous if and only if $R^k$ is unambiguous for all $k$ and $R^k\cap R^n=\varnothing$ for all $k\ne n$

Example

$(ϵ⌣0)(0⌣00)$

Notice $(ϵ⌣0)$ is unambiguous as $\{ϵ\}\cap \{0\}=\varnothing$. This has language $\{ϵ,0\}$

Similarly, $0⌣00$ is an unambiguous expression for $\{0,00\}$

Consider $(ϵ⌣0)(0⌣00)$

$\{ϵ,0\}\{0,00\}=\{ϵ.0,ϵ.00,0.0,0.00\}=\{0,00,000\}$

$\{ϵ,0\}\times \{0,00\}=\{(ϵ,0),(ϵ,00),(0,0),(0,00)\}$

In this case $\{ϵ,0\}\{0,00\}$ is size $3$ and $\{ϵ,0\}\times \{0,00\}$ is size $4$.

Hence there does not exist a bijection, and $(ϵ⌣0)(0⌣00)$ is ambiguous.

Theorem

Let $R$ and $S$ be unambiguous expressions with languages $\mathcal{R}$ and $\mathcal{S}$ and generating series ${\Phi }_{\mathcal{R}},{\Phi }_{\mathcal{S}}$ (with weight function $=$ length of binary string). $ϵ,0,1$ are unambiguous regular expressions with languages $\{ϵ\},\{0\},\{1\},$ and generating series

${\Phi }_{\{ϵ\}}(x)=x^{\text{length}(ϵ)}=x^0=1$ ${\Phi }_{\{0\}}(x)=x^{\text{length}}(0)=x^1=x.{\Phi }_{\{1\}}(x)=x^{\text{length}}(1)=x^1=x$

Sum Lemma

Assume $R⌣S$ is unambiguous, and is associated to the language $\mathcal{R}\cup \mathcal{S}$. Further

$$\begin{array}{r}{\Phi }_{\mathcal{R}\cup \mathcal{S}}(x)={\Phi }_{\mathcal{R}}(x)+{\Phi }_{\mathcal{S}}(x)\end{array}$$

Product Lemma

Assume $RS$ is an unambiguous expression for $\mathcal{R}\mathcal{S}$ (which has a bijection to $\mathcal{R}\times \mathcal{S}$). Further

$$\begin{array}{r}{\Phi }_{\mathcal{R}\mathcal{S}}(x)={\Phi }_{\mathcal{R}\times \mathcal{S}}(x)={\Phi }_{\mathcal{R}}(x)\cdot {\Phi }_{\mathcal{S}}(x)\end{array}$$

String Lemma

Assume $R^{\ast }$ is unambiguous with language $R^{\ast }$. Then

$$\begin{array}{r}{\Phi }_{{\mathcal{R}}^{\ast }}(x)=\frac{1}{1-{\Phi }_{\mathcal{R}}(x)}\end{array}$$

Example

The regular expression $0^{\ast }(100^{\ast }{)}^{\ast }(ϵ⌣1)$ is unambiguous.

Let $\mathcal{S}$ be the language represented by this expression. Find ${\Phi }_{\mathcal{S}}(x)$

$0$ has generating series ${\Phi }_{\{0\}}(x)=x$

$0^{\ast }$ has generating series ${\Phi }_{\{0{\}}^{\ast }}(x)=\frac{1}{1-{\Phi }_{\{0\}}(x)}=\frac{1}{1-x}$

Next

$$\begin{array}{rl}{\Phi }_{\{10\}\{0{\}}^{\ast }}(x)& ={\Phi }_{\{1\}}(x)\cdot {\Phi }_{\{0\}}(x)\cdot {\Phi }_{\{0{\}}^{\ast }}(x)\\ & =x\cdot x\cdot (\frac{1}{1-x})\\ & =\frac{x^2}{1-x}\end{array}$$

This gives the generating series associated to $(100^{\ast }{)}^{\ast }$ as

$$\begin{array}{r}\frac{1}{1-{\Phi }_{\{10\}\{0{\}}^{\ast }}(x)}=\frac{1}{1-\frac{x^2}{1-x}}\end{array}$$

Lastly ${\Phi }_{\{ϵ,1\}}(x)={\Phi }_{\{ϵ\}}(x)+{\Phi }_{\{1\}}(x)=1+x$ Hence

$$\begin{array}{rl}{\Phi }_{\mathcal{S}}(x)& =\frac{1}{1-x}\cdot \frac{1}{1-\frac{x^2}{1-x}}\cdot (1+x)\\ & =\frac{1+x}{1-x-x^2}\end{array}$$

Note

We can do this on ambiguous expressions, but the coefficients can include over-counts and be too high.

Block & Prefix Decomposition

We see that having an unambiguous regular expression allows us to construct a generating series for the language with respect to the length.

One way to do this is to decompose the strings in an unambiguous way, and construct the regular expression for this.

Block Decomposition

We will decompose a string into alternating “blocks” of 0’s and 1’s.

Example

$11010001110101$

$\mathrm{11.0.1.000.111.0.1.0.1}$

A non-empty block of $0$‘s can be represented by $00^{\ast }$. A non-empty block of $1$‘s can be represented by $11^{\ast }$.

If we alternate these, we could have, for example,

$00^{\ast }11^{\ast }00^{\ast }11^{\ast }00^{\ast }$

We can represent all binary strings by the unambiguous block decompositions

$1^{\ast }(00^{\ast }11^{\ast }{)}^{\ast }{0}^{\ast }$

or

$0^{\ast }(11^{\ast }00^{\ast }{)}^{\ast }{1}^{\ast }$

Example

Find a regular expression (unambiguous) where all blocks of 0 even length can be represented.

Notice a non-empty block of $0$‘s of even length can be represented by $00(00{)}^{\ast }$. If we also wanted to allow an empty block, we can use $(00{)}^{\ast }$

Binary Strings $1^{\ast }(00^{\ast }11^{\ast }{)}^{\ast }{0}^{\ast }$

New Set $1^{\ast }(\underset{\text{even length, non-empty}}{\underbrace{00(00{)}^{\ast }}}11^{\ast }{)}^{\ast }\underset{\text{even length, possibly empty}}{\underbrace{(00{)}^{\ast }}}$

Example

All blocks are odd length

Blocks of 1’s, possibly empty, of odd length

$ϵ⌣1(11{)}^{\ast }$

Blocks of 0’s, non-empty, odd length

$0(00{)}^{\ast }$

Blocks of 1’s, non-empty, odd length

$1(11{)}^{\ast }$

Block of 0’s, possibly empty, odd length

$(ϵ⌣0(00{)}^{\ast }$

All binary strings

$1^{\ast }(00^{\ast }11^{\ast }{)}^{\ast }{0}^{\ast }$

$(ϵ⌣1(11{)}^{\ast })(0(00{)}^{\ast }1(11{)}^{\ast }{)}^{\ast }(ϵ⌣0(00{)}^{\ast })$

New expression

Another common type of decomposition is called prefix decomposition.

Prefix Decomposition

The idea is every part starts with 1 and every 1 starts a part.

Example

$00110001001101$

$\mathrm{00.1.1000.100.1.10.1}$

Every part looks like $10^{\ast }$. We need to allow the word to start with some number of 0’s.

This gives us a decomposition of $0^{\ast }(10^{\ast }{)}^{\ast }$

(Note, we could decompose based on 0’s, or based on suffixes).

Example

Find an unambiguous regular expression where every 1 is followed by at least two 0’s.

Here $10^{\ast }$ is a 1 followed by any number of 0’s. We can modify this to give $1000^{\ast }$, where every 1 is followed by at least two 0’s.

All binary strings $0^{\ast }(10^{\ast }{)}^{\ast }$

New expression $0^{\ast }(1000^{\ast }{)}^{\ast }$

Aside

There are multiple ways to represent all binary strings. The easiest, but least useful is $(0⌣1{)}^{\ast }$.

Example

We have an unambiguous regular expression for all words where 1 is followed by at least two 0’s. Let this language by $\mathcal{R}$. Find ${\Phi }_{\mathcal{R}}(x)$.

Here the regular expression is $0^{\ast }(1000^{\ast }{)}^{\ast }$

Notice the generating series for the part coming from $0^{\ast }$ is $\frac{1}{1-x}$

The generating series corresponding to $1000^{\ast }$ is $\frac{x^3}{1-x}$.

Putting this together gives $(\frac{1}{1-x})(\frac{1}{1-\frac{x^3}{1-x}})$

This can be simplified to the form $\frac{\text{polynomial}}{\text{polynomial}}$.

Recursive Decomposition

Recursive Decomposition

Another way we can describe a language is recursively. It is possible that such a language is not a rational language. Despite this, we can often still use this decomposition to say something meaningful about the language via generating series.

We need this decomposition to be unambiguous for this to work.

Example

Let $\mathcal{S}$ be the set of binary strings where all blocks of 1’s are even, and all blocks of 0’s are of length divisible by 3.

For any word in $\mathcal{S}$, either it is $ϵ$, or it starts with 0, or it starts with 1. As all blocks of 0 have length divisible by 3, if it starts with 0, then it has to start with $000$. Similarly, if it starts with 1, it in fact starts with $11$.

Here if $S$ is the “regular expression”, then we have

$S=(ϵ⌣11S⌣000S)$

This allows us to say something about the generating series.

$$\begin{array}{rl}{\Phi }_{\mathcal{S}}(x)& ={\Phi }_{\{ϵ\}}(x)+{\Phi }_{\{11\}}(x){\Phi }_{\{\mathcal{S}\}}(x)+{\Phi }_{\{000\}}(x)+{\Phi }_{\{\mathcal{S}\}}(x)\\ & =1+x^2\cdot {\Phi }_{\mathcal{S}}(x)+x^3\cdot {\Phi }_{\mathcal{S}}(x)\\ & ⟹{\Phi }_{\mathcal{S}}(x)-x^2{\Phi }_{\mathcal{S}}(x)-x^3{\Phi }_{\mathcal{S}}(x)=1\end{array}$$

Hence

$$\begin{array}{r}{\Phi }_{\mathcal{S}}(x)(1-x^2-x^3)=1\text{ or}\\ {\Phi }_{\mathcal{S}}(x)=\frac{1}{1-x^2-x^3}\end{array}$$

Note

This language is in fact rational, and has block decomposition

$(11{)}^{\ast }(000(000{)}^{\ast }(11)(11{)}^{\ast }{)}^{\ast }(000{)}^{\ast }$

Example

Let $\mathcal{R}=\{0^n{1}^n{\}}_{n=0}^{\infty }=\{ϵ,01,0011,000111,\dots \}$

We see $\mathcal{R}$ is either empty, $ϵ$, or it starts with a 0 and ends with a 1, and the middle part (after removing the first and last term) is in $\mathcal{R}$.

This gives us $R=0R1⌣ϵ$

Hence the generating series looks like

$$\begin{array}{rl}{\Phi }_{\mathcal{R}}(x)& ={\Phi }_{\{ϵ\}}(x)+{\Phi }_{\{0\}}(x){\Phi }_{\{\mathcal{R}\}}(x){\Phi }_{\{1\}}(x)\\ & ⟹{\Phi }_{\mathcal{R}}(x)=1+x{\Phi }_{\mathcal{R}}(x)x\\ & ⟹{\Phi }_{\mathcal{R}}(x)(1-x^2)=1\\ & ⟹{\Phi }_{\mathcal{R}}(x)=\frac{1}{1-x^2}=1+x^2+x^4+x^6+\dots \end{array}$$

Example

Let $\mathcal{R}$ be the language that does not contain $001$. It is useful to define $\mathcal{S}$ as the language that contains $001$ exactly once, at the very end. Let $R$ and $S$ be their expressions.

Notice $\mathcal{R}\cap \mathcal{S}=\varnothing$

Consider $R\cup S$.

This is either $ϵ$, or ends in 0, or ends in 1.

If it ends in 0, and we remove the final 0, then it will still not contain $001$ (i.e. it is in $\mathcal{R})$

If it ends in 1, and we remove the final 1, then it will not contain $001$ and hence is in $\mathcal{R}$.

This gives $R⌣S=ϵ⌣R0⌣R1$

$$\begin{array}{rl}⟹{\Phi }_{\mathcal{R}}(x)+{\Phi }_{\mathcal{S}}(x)& ={\Phi }_{\{ϵ\}}(x)+{\Phi }_{\mathcal{R}}(x){\Phi }_{\{0\}}(x)+{\Phi }_r(x){\Phi }_{\{1\}}(x)\\ & =1+{\Phi }_{\mathcal{R}}\cdot x+{\Phi }_{\mathcal{R}}(x)\cdot x\\ & =1+2x{\Phi }_{\mathcal{R}}(x)\end{array}$$

Consider a word $r_1{r}_2\dots r_{n}001$ represented by $S$. This cannot contain a $001$ anywhere in $r_1{r}_2\dots r_{n}00$ by assumption.

As $00$ at the end cannot create a $001$, we see $r_1{r}_2\dots r_{n}00$ does not contain a $001$ if and only if $r_1{r}_2\dots r_n$ does not contain a $001$.

This gives us $S=R001$

Hence ${\Phi }_{\mathcal{S}}(x)=x^3{\Phi }_{\mathcal{R}}(x)$

Combining the two equations gives

$$\begin{array}{r}{\Phi }_{\mathcal{R}}(x)+x^3{\Phi }_{\mathcal{R}}(x)-2x{\Phi }_{\mathcal{R}}(x)=1\\ ⟹{\Phi }_{\mathcal{R}}(x)=\frac{1}{1-2x+x^3}\end{array}$$

Example

Same as before, except use $000$ instead of $001$.

As before we have

$$\begin{array}{r}{\Phi }_{\mathcal{R}}(x)+{\Phi }_{\mathcal{S}}(x)=1+2x{\Phi }_{\mathcal{R}}(x)\end{array}$$

The problem occurs when we try to do something like $S=R001$.

Consider $00\in \mathcal{R}$

We see $00.000\notin \mathcal{S}$

We see $\underline{000}00,0\underline{000}0,00\underline{000}$ has multiple occurrences of $000$, two of them not at the end.

If $r_1\dots r_n=r_1{r}_2\dots r_{n-2}00\in \mathcal{R}$

Then $r_1{r}_2\dots r_{n}000=\underset{\in \mathcal{S}}{\underbrace{(r_1{r}_2\dots r_{n-2}000)}}(00)\in \mathcal{S}(00)$

If $r_1{r}_2\dots r_n=r_1{r}_2\dots r_{n-1}0\in \mathcal{R}$ $⟹r_1{r}_2\dots r_{n-1}0000=(\underset{\in \mathcal{S}}{\underbrace{r_1{r}_2\dots r_{n-1}000}})(0)\in \mathcal{S}0$

This gives

$S⌣S0⌣S00=R000$

$$\begin{array}{rl}& ⟹{\Phi }_{\mathcal{S}}(x)(1+x+x^2)=x^3{\Phi }_{\mathcal{R}}(x)\\ & ⟹{\Phi }_{\mathcal{R}}(x)+\frac{x^3}{1+x+x^2}{\Phi }_{\mathcal{R}}(x)=1+2x{\Phi }_{\mathcal{R}}(x)\\ & ⟹{\Phi }_{\mathcal{R}}(x)=\frac{1+x^2+x^3}{1-x-x^2-x^3}\end{array}$$

Excluded Substrings

Theorem

Let $\kappa \in \{0,1{\}}^{\ast }$ be a non-empty binary string of length $n$. Let $\mathcal{C}$ be the collection of non-empty suffixes $\gamma$ of $\kappa$ such that there exists a $n\kappa =\kappa \gamma$.

Let $C(x)={\sum }_{\gamma \in \mathcal{C}}{x}^{\ell (\gamma )}$

Then the generating series for the language of binary strings not containing $\kappa$ is

$$\begin{array}{r}\Phi (x)=\frac{1+C(x)}{(1-2x)(1+C(x))+x^n}\end{array}$$

Example

Let $k=000.n=\ell (000)=\ell (\kappa )=3$

Notice the suffixes of $\kappa$ are $00$ and $0$. In this case

$0.000=000.0$.

$00.000=000.00$

In this case $\mathcal{C}=\{0,00\}$

This gives $C(x)=x^{\ell (0)}+x^{\ell (00)}=x+x^2$

This gives

$$\begin{array}{rl}\Phi (x)& =\frac{1+x+x^2}{(1-2x)(1+x+x^2)+x^3}\\ & =\frac{1+x+x^2}{1-x-x^2-x^3}\end{array}$$

Why does this work?

In the original method we always have

$R⌣S=ϵ⌣R0⌣R1$

($R$-language avoiding $\kappa$. $R$-language containing exactly one $\kappa$ at the end).

The second relationship depends on $\mathcal{C}$. Let $\mathcal{C}=\{{\gamma }_1,\dots ,{\gamma }_{\kappa }\}$

We get a new relation

$$\begin{array}{r}R\kappa =S⌣S{\gamma }_1⌣S{\gamma }_2⌣\dots ⌣S{\gamma }_{\kappa }\end{array}$$

From these two relations we get the generating series

$$\begin{array}{r}{\Phi }_{\mathcal{R}}(x)+{\Phi }_{\mathcal{S}}(x)=1+2x{\Phi }_{\mathcal{R}}(x)\end{array}$$

and

$$\begin{array}{rl}{x}^n{\Phi }_{\mathcal{R}}(x)& ={\Phi }_{\mathcal{S}}(x)+x^{\ell (\gamma )}{\Phi }_{\mathcal{S}}(x)+\dots +x^{\ell ({\gamma }_{\kappa })}{\Phi }_{\mathcal{S}}(x)\\ & =(1+C(x)){\Phi }_{\mathcal{S}}(x)\end{array}$$

So

$${\Phi }_{\mathcal{S}}(x)=\frac{x^n}{1+C(x)}\cdot {\Phi }_{\mathcal{R}}(x)$$

After this it is just algebraic manipulation to solve for ${\Phi }_{\mathcal{R}}(x)$.

Example

Let $\kappa =1010$

$\mathcal{R}$ - avoid $\kappa$

$\mathcal{S}$ - $\kappa$ occurs exactly once at the end

$R⌣S=ϵ⌣R0⌣R1$

What happens if we append $\kappa$ to the end of a word in $R$.

If the word in $R$ ended with $10$, then

$r_1{r}_2\dots r_{k}10\kappa =r_1{r}_2\dots r_{k}101010$

This is in $S10$.

In this case the $10$ corresponds to a $\gamma \in \mathcal{C}$ as $10\kappa =\kappa 10=101010$

If the word does not end in $10$, then we are fine, and $r_1{r}_2\dots r_{n}1010\in \mathcal{S}$

Notice, the suffixes of $\kappa =1010$ are $010,10,0.$

$n\kappa \ne \kappa 0=10100$

$10\kappa =\kappa 10=101010$

$n\kappa \ne \kappa 010=1010010$

From here we get

$R\kappa =S⌣S10$

Recurrence Relations

Recurrences

Example

Let $g_0=1,g_1=1$ and $g_n=2g_{n-1}+g_{n-2}\forall n\ge 2$

Questions

What can we say about

$$\begin{array}{r}\sum _{n=0}^{\infty }{g}_n{x}^n\end{array}$$

Can we find a closed form for it? What can we do with this closed form?

First, find a closed form for

$$\begin{array}{rl}G(x)& =\sum _{n=0}^{\infty }{g}_n{x}^n\\ & =1+x+\sum _{n=2}^{\infty }{g}_n{x}^n\\ & =1+x+\sum _{n=2}^{\infty }(2g_{n-1}{x}^n+g_{n-2})x^n\\ & =1+x+\sum _{n=2}^{\infty }2g_{n-2}{x}^n+\sum _{n=2}^{\infty }{g}_{n-2}{x}^n\\ & =1+x+\sum _{n=2}^{\infty }2g_{n-1}{x}^n+x^2\sum _{n=0}^{\infty }{g}_n{x}^n\\ & =1+x+\sum _{n=2}^{\infty }2g_{n-1}{x}^n+x^{2}G(x)\\ & =1+x+2x\sum _{n=2}^{\infty }{g}_{n-1}{x}^{n-1}+x^{2}G(x)\\ & =1+x+2x(-g_0{x}^0+\sum _{n=1}^{\infty }{g}_{n-1}{x}^{n-1})+x^{2}G(x)\\ & =1+x+2x(-1+G(x))+x^{2}G(x)\\ & =1+x-2x+2xG(x)+x^{2}G(x)\\ & ⟹G(x)=1-x+2xG(x)+x^{2}G(x)\\ & ⟹G(x)(1-2x-x^2)=1-x\\ & ⟹G(x)=\frac{1-x}{1-2x-x^2}\end{array}$$

This is our desired closed form expression.

Example

Let $g_0=g_1=1$, and $g_n=2g_{n-1}+g_{n-2}\forall n\ge 2$

Last class we showed

$$\begin{array}{r}G(x)=\sum _{n=0}^{\infty }{g}_n{x}^n=\frac{1-x}{1-2x-x^2}\end{array}$$

Consider $1-2x-x^2$. I want to write this as $(1-\alpha x)(1-\beta x)$ for reasons that will make sense later.

Find the roots of $y^2-2y-1$.

(This is $y^{2}P(\frac{1}{y})$ where $P(x)=1-2x-x^2$)

By the quadratic formula, the roots of $y^2-2y-1$ are $\frac{2\pm \sqrt{4+4}}{2}=1\pm \sqrt{2}$.

This gives $y^2-2y-1=(y-(1+\sqrt{2}))(y-(1-\sqrt{2}))$.

Equiv: $1-2x-x^2=(1-(1+\sqrt{2})x)(1-(1-\sqrt{2})x)$

This gives us

$$\begin{array}{r}\frac{1-x}{1-2x-x^2}=\frac{1-x}{(1-(1+\sqrt{2})x)(1-(1-\sqrt{2})x)}\end{array}$$

We can now do a partial fraction decomposition (Math $138$).

That is, we can find an $a$ & $b$ such that

$$\begin{array}{r}\frac{1-x}{(1-(1+\sqrt{2})x)(1-(1-\sqrt{2})x)}=\frac{a}{(1-(1+\sqrt{2})x)}+\frac{b}{(1-(1-\sqrt{2})x)}\end{array}$$

Multiplying both sides by the denominator gives $1-x=a(1-(1-\sqrt{2})x)+b(1-(1+\sqrt{2})x)$

With a bit of trial and error, we see $a=\frac{1}{2}$ and $b=\frac{1}{2}$.

This gives us,

$$\begin{array}{rl}G(x)=\sum _{n=0}^{\infty }{g}_n{x}^n=\frac{1-x}{1-2x-x^2}& =\frac{\frac{1}{2}}{(1-(1+\sqrt{2})x)}+\frac{\frac{1}{2}}{(1-(1-\sqrt{2})x)}\\ & =\frac{1}{2}\sum _{n=0}^{\infty }(1+\sqrt{2}{)}^n{x}^n+\frac{1}{2}\sum _{n=0}^{\infty }(1-\sqrt{2}{)}^n{x}^n\\ & =\sum _{n=0}^{\infty }\frac{1}{2}((1+\sqrt{2}{)}^n+(1-\sqrt{2}{)}^n)x^n\\ \text{This gives us }{g}_n& =\frac{1}{2}((1+\sqrt{2}{)}^n+(1-\sqrt{2}{)}^n).\end{array}$$

We notice in this case that $1-\sqrt{2}\approx -0.44$. This means that $(1-\sqrt{2}{)}^n\to 0$ as $n\to \infty$.

This means for large $n$ that

$$\begin{array}{r}{g}_n\approx \frac{1}{2}(1+\sqrt{2}{)}^n\end{array}$$

Further, as $g_n$ are all integers, we see $\frac{1}{2}(1+\sqrt{2}{)}^n$ is very close to an integer for large $n$.

Homogeneous Linear Recurrence Relations

Let $a_1,a_2,\dots ,a_d$ be a set of complex numbers (typically integers).

Let $g_0,g_1,\dots ,g_m$ be a set of initial conditions. Here $m\ge d-1$.

Then the sequence $g_1,g_2,\dots$ is a homogeneous linear recurrence relation if for all $n\ge m+1$ we have

$$\begin{array}{r}{g}_n+a_1{g}_{n-1}+\dots +a_d{g}_{n-d}=0\end{array}$$

Example

Our previous example is an example of such a relation. Here $g_1=g_0=1$, and

$$\begin{array}{r}{g}_n-2g_{n-1}-g_{n-2}=0,\forall n\ge 2\end{array}$$

Here $a_1=-2,a_2=-1$. In the previous example, we had

$$\begin{array}{r}G(x)=\sum _{n=0}^{\infty }{g}_n{x}^n=\frac{P(x)}{(1+a_{1}x+a_2{x}^2)}\text{for some polynomial }P(x)\end{array}$$

Theorem

Let $g_n+a_1{g}_{n-1}+\dots +a_d{g}_{n-d}=0$ be the recurrence relation. Then

$$\begin{array}{r}G(x)=\frac{b_m{x}^m+\dots b_0}{1+a_{1}x+a_2{x}^2+\dots +a_d{x}^d}\end{array}$$

where $b_k=g_k+a_1{g}_{k-1}+\dots +a_d{g}_{k-d}$ here $g_n=0$ if $n<0$.

Example

Let

$$\begin{array}{r}G(x)=\sum _{n=0}^{\infty }{g}_n{x}^n=\frac{2x^2-4x+3}{(1-2x{)}^2(1+x)}\end{array}$$

1. Find a closed form for $g_n$

2. Find initial conditions

3. Find recurrence relations

We know from partial fraction decomposition that there exists $a,b,$ and $c$ such that

$$\begin{array}{r}\frac{2x^2-4x+3}{(1-2x{)}^2(1+x)}=\frac{a}{(1-2x)}+\frac{b}{(1-2x{)}^2}+\frac{c}{(1+x)}\end{array}$$

Multiply by denominator

$$\begin{array}{r}2x^2-4x+3=a(1-2x)(1+x)+b(1+x)+c(1-2x{)}^2\end{array}$$

Evaluate at $x=-1$ gives, $c=1$

Evaluate at $x=\frac{1}{2}$ gives $b=1$.

Knowing $c=1$ and $b=1$ we can simplify and get $a=1$.

Hence

$$\begin{array}{r}\frac{2x^2-4x+3}{(1-2x{)}^2(1+x)}=\frac{1}{1-2x}+\frac{1}{(1-2x{)}^2}+\frac{1}{1+x}\end{array}$$

This gives

$$\begin{array}{rl}G(x)& =\sum _{n=0}^{\infty }{2}^n{x}^n+\frac{1}{(1-2x{)}^2}+\sum _{n=0}^{\infty }(-1{)}^n{x}^n\\ & =\sum _{n=0}^{\infty }{2}^n{x}^n+\sum _{n=0}^{\infty }\left(\genfrac{}{}{0ex}{}{n+1}{1}\right)2^n{x}^n+\sum _{n=0}^{\infty }(-1{)}^n{x}^n\\ & =\sum _{n=0}^{\infty }(2^n+(n+1)2^n+(-1{)}^n)x^n\\ & =\sum _{n=0}^{\infty }(2\cdot 2^n+n{2}^n+(-1{)}^n)x^n\end{array}$$

Hence

$$\begin{array}{rl}& g_0=2\cdot 2^0+0\cdot 2^0+(-1{)}^0=3\\ & g_1=2\cdot 2^1+1\cdot 2^1+(-1{)}^1=5\\ & g_2=17\end{array}$$

Notice

$$\begin{array}{rl}& (1-2x{)}^2(1+x)\\ & =(1-4x+4x^2)(1+x)\\ & =(1-3x+0+4x^3)\\ & ⟹g_n=3g_{n-1}+0g_{n-2}+4g_{n-3}\\ & ⟹g_n=3g_{n-1}-4g_{n-3}\end{array}$$

Linear Homogeneous Recurrence Equations

Version 1

Initial conditions $g_0,g_1,\dots ,g_{d-1}$

Recurrence Equation $g_n+a_1{g}_{n-1}+\dots +a_d{g}_{n-d}=0,\forall n\ge d$

Version 2

$$\begin{array}{r}G(x)=\sum _{n=0}^{\infty }{g}_n{x}^n=\frac{P(x)}{Q(x)}\end{array}$$

Here, $Q(x)=1+a_1{x}^1+a_2{x}^2+\dots a_d{x}^d$

Version 3

Assume

$$\begin{array}{r}Q(x)=(1-{\lambda }_{1}x{)}^{{\alpha }_1}(1-{\lambda }_{2}x{)}^{{\alpha }_2}\dots (1-{\lambda }_{k}x{)}^{{\alpha }_k}\end{array}$$

Then there exists polynomials $P_1(x),P_2(x),\dots ,P_k(x)$ with $deg{P}_i(x)\le {\alpha }_i-1$ such that

$$\begin{array}{r}{g}_n=P_1(n){\lambda }_1^n+P_2(n){\lambda }_2^n+\dots +P_k(n){\lambda }_k^n\end{array}$$

Introduction to Graph Theory

Note, embedded graphs are not complete yet. For the full graph theory notes (including the graphs) check the pdf

Definitions

Definition

A graph $G$ is a collection of vertices, ($V(G)$), say $\{v_1,\dots ,v_n\}$ and a collection of unordered pairs (edges) between the vertices, $E(G)=\{(v_{i_1},v_{j_1}),(v_{i_2},v_{j_2}),\dots \}$.

For now, we assume the number of vertices is finite. We will assume that there is at most one edge between two vertices. We will assume the edges are undirected (i.e. pairs are unordered). We will assume that there are no edges from a vertex to itself.

Graph

Example

Let $G$ be a graph with

$V(G)=\{1,2,3,4\}$ and

$E(G)=\{(1,2),(1,3),(1,4),(2,4),(3,4)\}$

We often draw graphs with circles around each vertex, and lines between two vertices indicating an edge.

We say two vertices are adjacent if there is an edge between them. For example $1$ & $2$ are adjacent, $2$ & $3$ are not.

We define the neighbours of a vertex to be all the vertices that it is adjacent to.

Example

The neighbours of $2$ are $1$ & $4$

If we can draw the graph in such a way that no edges cross each other, then that graph is called planar. The previous example is planar.

Example

The graph $G$ on five vertices, and an edge between every pair of vertices is not planar.

In this case, if we remove any edge, the new graph is planar.

There are a huge number of applications to graph theory.

1. Networks
2. Traveling Salesperson Problem
3. Colouring countries on a map

There are a lot of variations (which are all interesting)

1. Multiple edges
2. Loops
3. Directions
4. Weights
5. Infinite graphs
6. We could allow unordered types (instead of pairs)

Definition

We say that the degree of a vertex $\mathrm{deg}(v)$ is the number of edges touching the vertex.

Fact

The degree of $v$ is equal to the number of neighbours of $v$.

Proof

At the other edge of an edge touching $v$ is a neighbour of $v$.

Theorem

$$\begin{array}{r}\sum _{v\in V(G)}\mathrm{deg}(v)=2|E(G)|\end{array}$$

Proof

We see each edge is connected to two vertices, say $v_1$ & $v_2$. Hence each edge contributes $1$ to the degree of $v_1$ and $1$ to the degree of $v_2$. This gives the equation.

Corollary

The number of vertices with odd degree is even.

Recall that we showed

${\sum }_{v\in V(G)}\mathrm{deg}(v)=2|E(G)|$

The right hand side is an even number.

Hence ${\sum }_{v\in V(G)}\mathrm{deg}(v)$ must be even.

If we had an odd number of vertices of odd degree, then ${\sum }_{v\in V(G)}\mathrm{deg}(v)$ would be odd.

Hence we have an even number of vertices of odd degree.

Corollary

The average degree of a vertex is

$$\begin{array}{r}\frac{2|E(G)|}{|V(G)|}\end{array}$$

Proof

Average degree

$$\begin{array}{r}\frac{1}{|V(G)|}\sum _{v\in V(G)}\mathrm{deg}(v)=\frac{2|E(G)|}{|V(G)|}\end{array}$$

Isomorphism

Definition

Let $G_1$ and $G_2$ be graphs. We say $G_1$ is isomorphic to $G_2$ ($G_1\simeq G_2$) if there exists a bijection $f:V(G_1)\to V(G_2)$ with the additional property that

$$\begin{array}{r}(v_1,v_2)\in E(G_1)⟺(f(v_1),f(v_2))\in E(G_2)\end{array}$$

Example

To see these are isomorphic, consider the bijection

$$\begin{array}{r}A⟶4\\ B⟶3\\ C⟶5\\ D⟶2\\ E⟶1\end{array}$$

This is easy to see there is a bijection from $V(G_1)$ to $V(G_2)$

We can check the edges

$$\begin{array}{rl}E(G_1)& ⟶E(G_2)\\ (A,D)& ⟶(4,2)\\ (E,A)& ⟶(1,4)\\ (E,B)& ⟶(1,3)\\ (E,C)& ⟶(1,5)\\ (E,B)& ⟶(1,2)\end{array}$$

Fact

Let $G_1$ and $G_2$ be isomorphic with bijection $f:V(G_1)\to V(G_2)$.

Then

1. They have the same number of vertices
2. Same number of edges
3. $\mathrm{deg}(v)=\mathrm{deg}(f(v))$

Which are isomorphic? Which are not?

	$G_1$	$G_2$	$G_3$	$G_4$	$G_5$
Edges	$5$	$4$	$5$	$4$	$4$
Vertices	$4$	$4$	$5$	$4$	$4$
# of vertices with $\mathrm{deg}=1$	$0$	$1$	$2$	$1$	$0$
Based on this information, the only two graphs that might be isomorphic are $G_2$ and $G_4$.

Example

These are not isomorphic despite having the same number of edges, vertices, and all vertices having the same degree ($3$).

Definition

We say a graph is $k-$regular if $\mathrm{deg}(v)=k$ for all $v\in V(G)$. We say a graph is regular if it is $k-$regular for some $k$.

Example

The graph with $1$ vertex and no edges is $0-$regular.

The graph with $n$ vertices and no edges is $0-$regular.

Example

What do the $1-$regular graphs look like?

$1$-regular graph with $2$ vertices.

As the number of vertices of odd degree is even, and $1$ is odd, we have that $1$-regular graphs have an even number of vertices.

$1$ regular graph with $4$ vertices.

In general, a $1$ regular graph looks like

Example

What do $2$-regular graphs look like?

$2$ regular graphs are a collection of disjoint cycles.

Example

What is the smallest $k-$regular graph (i.e. minimal vertices)? ($k+1$)

Let $V(G)=\{1,2,\dots ,k+1\}$ and put an edge between every pair of vertices.

Definition

A complete graph ${\mathcal{K}}_n$ is a graph with $n-$vertices and an edge between every vertex.

Note $\mathcal{K}$ is $(n-1)-$regular

Question

How many edges does ${\mathcal{K}}_n$ have?

We know there are $n-$vertices, and every vertex has degree $n-1$.

This gives

$$\begin{array}{rl}2|E(G)|=\sum _{v\in V(G)}\mathrm{deg}(v)& =\sum _{v\in V(G)}n-1\\ & =n\cdot (n-1)\\ ⟹|E(G)|=\frac{n(n-1)}{2}& \end{array}$$

Bipartite Graphs

Definition

We say $G$ is a bipartite graph if we can divide the vertices $V(G)$ into two disjoint sets $A$ and $B$ such that all edges have one end in $A$ and one end in $B$.

Example

Which of the following are bipartite ($G_1$, $G_2$, $G_3$ respectively)?

$G_1$ is bipartite. To see this, let $A=\{1,4\}$ and $B=\{2,3\}$

$G_2$ is not bipartite. To see this, assume it is, and hope for a contradiction. Assume without loss of generality that $1\in A$. As there is an edge from $1$ to $5$ and $1$ to $2$, as there are no edges from $A$ to $A$, we see $2,5\in B$. There is an edge from $5$ to $4$, hence $4\in A$. Similarly, there is an edge between $2$ and $3$. Hence, $3\in A$. But there is an edge from $3$ to $4$, both in $A$.

This gives us a contradiction. Hence $G_2$ is not bipartite.

For $G_3$ we can assume a vertex is in $A$, and see what we derive.

Example

Let $G$ be a $1$-regular graph on $10$ vertices.

This is bipartite. To see this, we could set $A=\{1,3,5,7,9\},B=\{2,4,6,8,10\}$

OR

$A=\{1,4,5,8,9\},B=\{2,3,6,7,10\}$

Example

Let $G$ be a graph on $100$ vertices, $V(G)=\{1,2,3,\dots ,100\}$

We say $(v_1,v_2)\in E(G)$ if and only if $|v_1-v_2|=1$ or $|v_1-v_2|=3$

The first couple vertices of this graph are

We see that odd numbers are not connected to each other, and even numbers are not connected to each other. We can take

$A=\{1,3,5,\dots ,99\}B=\{2,4,6,\dots ,100\}$

Note

Technically “connected” has meaning in graph theory. It is better to say there is no edge between two odd vertices.

Definition

We say $G$ is a complete bipartite graph if it is bipartite, and every vertex in $A$ has an edge to every vertex in $B$.

This is typically denoted ${\mathcal{K}}_{n,m}$ where $|A|=n,|B|=m$.

${\mathcal{K}}_{2,2},{\mathcal{K}}_{2,3},{\mathcal{K}}_{3,3}$ respectively.

Question

How many vertices does ${\mathcal{K}}_{n,m}$ have?

We see $n=|A|,m=|B|$ and $V(G)$ is a disjoint union of $A$ and $B$. So $|V(G)|=m+n$.

The number of edges is $m\cdot n$. To see this, note that there are $n$ vertices in $A$. Further, every vertex has an edge to all $m$ vertices in $B$. There are no other edges. Hence there are $n\cdot m$ edges.

Theorem

Let $G_1$ be isomorphic to $G_2$. Then $G_1$ is bipartite $⟺G_2$ is bipartite.

Proof

To see this, let $f:V(G_1)\to V(G_2)$ be an edge-preserving bijection. Then if $A,B$ demonstrate $G_1$ is bipartite, $f(A),f(B)$ will demonstrate $G_2$ is bipartite.

Example

Consider the 3-regular graphs on 6-vertices.

We see $G_2$ is bipartite (and is isomorphic to ${\mathcal{K}}_{3,3}$ using $A=\{1,2,3\},B=\{4,5,6\}$).

$G_1$ is not bipartite. To see this, assume $1\in A$. Then $2,3\in B$. But there is an edge from $2$ to $3$. A contradiction.

Example

Let ${\mathcal{K}}_{n,m}$ be a $k-$regular bipartite graph. Show $n=m$ or $k=0$.

If ${\mathcal{K}}_{n,m}$ is $k-$regular, we see every vertex in $A$ has degree $k$.

So there are $k\cdot n$ edges.

Similarly, looking at $B$, we have $k\cdot m$ edges.

This gives $kn=km$, hence $k=0$ or $m=n$.

Specifying Graphs

1) Draw a picture

2) Specify the vertices and edges.

$V(G)=\{1,2,3\}$

$E(G)=\{(1,2),(1,3)\}$

3) Giving the vertices, and a rule for the edges.

Example

Let $V(G)$ be the set of all subsets of $\{1,2,3\}$

We say $(A,B)\in E(G)$ if $A\cap B=\varnothing$

Adjacency Matrix

This is a $|V(G)|\times |V(G)|$ matrix, with columns/rows induced by $V(G)$.

We set $M[i,j]=1$ if $(i,j)\in E(G)$ and 0 otherwise.

Example

$$\left[\begin{array}{cccc}0& 1& 1& 0\\ 1& 0& 1& 0\\ 1& 1& 0& 1\\ 0& 0& 1& 0\end{array}\right]$$

As there are no loops, all terms on the diagonal are $0$. As the graph is undirected, $M=M^{\top }$. As we do not allow multiple edges, entries are bounded by $1$.

Powers of these matrices tell us information about walks.

This is annoying if $|V(G)|$ is large.

Adjacency List

Vertex	Neighbours
$A$	$BC$
$B$	$AC$
$C$	$ABD$
$D$	$C$

Paths and Cycles

Definition

Let $G$ be a graph. We define a walk from $v_0$ to $v_n$ as a sequence of vertices $v_0,v_1,v_2,\dots ,v_{n-1},v_n$ such that $(v_i,v_{i+1})\in E(G)$ for $i=0,1,\dots ,n-1$. This is a walk of length $n$ (as there are $n-$edges).

Example

Find all walks of length $2$ starting at $1$ of

$$\begin{array}{r}1-3-21-3-1\\ 1-2-31-2-4\\ 1-2-11-3-4\end{array}$$

Definition

A path is a walk where all vertices are distinct.

Example

For the previous graph, there are $4$ paths of length $2$ starting at $1$.

They are $1-2-3,1-3-2,1-2-4,1-3-4$

Fact

The longest path in a graph $G$ has at most length $|V(G)|-1$

Example

The longest path is length $1$, even though we have $|V(G)|=4$

Theorem

If there exists a walk from $x$ to $y$ then there exists a path from $x$ to $y$.

Proof

If $x=y$, we are done. Take the path of length $0$ starting/ending at $x$.

Let $x-v_1-v_2-\dots -v_{n-1}-y$ be a walk from $x$ to $y$. If all vertices are distinct, we are done. Hence assume $v_i=v_j$ for $i\ne j$ (with $v_0=x,v_n=y)$. Assume $i<j$.

Consider the new walk

$$\begin{array}{rl}x=& v_0-v_1-v_2-\dots -v_i-v_{j+1}-v_{j+2}-\dots -v_n\\ & \text{(Remove everything between }{v}_1\text{ and }{v}_{j+1}\text{)}\end{array}$$

Either this new walk has all vertices distinct, or we repeat.

Note, the initial walk is a finite length. Every time we apply this process we get something shorter. This process will eventually terminate.

Example

$$\begin{array}{rl}& 1-2-3-2-4-3-2-1-3-4\\ & 1-2-3-2-1-3-4\\ & 1-3-4\end{array}$$

Alternatively

$$\begin{array}{rl}& 1-2-3-2-4-3-2-1-3-4\\ & 1-2-3-4\end{array}$$

Theorem

If there is a path from $x$ to $y$ and from $y$ to $z$ then there is a path from $x$ to $z$.

$$\begin{array}{rl}x-v_1-\dots -& v_{n-1}-y-u_1-u_2-\dots -u_{m-1}-z\\ & \text{is a walk from }x\text{ to }z\end{array}$$

We can use the previous result to get a path.

Definition

Let $G_1$ and $G_2$ be graphs. We say $G_1$ is a subgraph of $G_2$ if $V(G_1)\subseteq V(G_2)$ and $E(G_1)\subseteq E(G_2)$.

Example

Which of these graphs are subgraphs of another graph?

$G_1,G_2,G_3,$ and $G_4$ are subgraphs of $G_4$.

$G_3$ is a subgraph of both $G_1$ and $G_2$.

Everything is a subgraph of itself.

Note

Let $G_1$ be a subgraph of $G_2$ (not example above)

• $|E(G_1)|\le |E(G_2)|$

• $|V(G_1)|\le |V(G_2)|$

• If $G_2$ is bipartite, then $G_1$ is (probably) bipartite. This won’t work if we remove all of $A$ or all of $B$ from $V(G_2)$.

• Every graph $G_1$ is a subgraph of the complete graph on vertices $V(G_1)$.

Definition

If $G_1$ is a subgraph of $G_2$ and $V(G_1)=V(G_2)$, then we say $G_1$ is a spanning subgraph of $G_2$.

If in addition, $E(G_1)\ne E(G_2)$ then $G_1$ is a proper spanning subgraph.

Fact

A spanning subgraph of a bipartite graph is bipartite.

Definition

A connected 2-regular subgraph is called a cycle.

Example

Find some cycles in

Theorem

Let $G$ be a graph such that $\mathrm{deg}(v)\ge 2$ for all $v\in V(G)$

Then $G$ contains a cycle.

Proof

Let $v_1-v_2-v_3-\dots -v_n$ be a path of maximal length. Notice, $\mathrm{deg}(v_n)\ge 2$.

Say $(v_n,x)\in E(G),x\ne v_{n-1}$. If $x\ne v_i$ for all $i=1,2,\dots ,n-1$, then $v_1-v_2-v_3-\dots -v_n-v_x$ is a longer path (which contradicts the fact that we took the longest path).

Hence $x=v_i$ for some $i=1,2,\dots ,n-1$

We have by assumption that $i\ne n-1$.

This gives us a cycle $v_1-v_{i+1}-\dots -v_n-v_i$

(Technically a walk contains more information than a cycle, as there is a concept of direction and start and end. By this we can mean the image of the walk).

Example

Step 1

Find a longest path ($1-4-2-5-3-6$).

Step 2

$6$ is connected to something. Say $2$.

Connect $2$ to $6$ and remove everything from the path before $2$.

Walk $2-5-3-6-2$

Definition

We say the girth of a graph is the size of the smallest cycle.

Definition

We say a cycle is a Hamiltonian cycle if it contains every vertex.

Definition

A path is a Hamiltonian path if it visits every vertex.

Example

The girth is $g(G)=3$ (given by $1-2-4-1$)

$1-2-3-6-5-4$ is a Hamiltonian path

$1-2-3-6-5-4-1$ is a Hamiltonian cycle

Exercise

Let ${\mathcal{K}}_n$ be a complete graph on $n-$vertices. How many cycles of size $3$ does ${\mathcal{K}}_n$ contain? Size $4$? Any size?

Fact

Let $G_1$ be isomorphic to $G_2$. Then

1. $g(G_1)=g(G_2)=girth(G_1)=girth(G_2)$
2. $G_1$ has a Hamiltonian path/cycle if and only if $G_2$ does.

Connectedness

Definition

Let $G$ be a graph. We say $G$ is connected if for all $v,u\in V(G)$, there exists a path from $v$ to $u$.

Example

is the only $1$-regular connected graph.

$2$-regular connected graphs include

These are the only examples.

A complete graph is always a connected graph.

This is true because there is always a path (of length $1$) between two vertices.

Theorem

Let $G$ be a graph. Let $v\in V(G)$ be such that there is a walk from $v$ to $u$ for all $w\in V(G)$. Then $G$ is connected.

Proof

Let $u,w\in V(G)$. We know there exists a walk $u-u_2-u_3-\dots -u_{n-1}-v$. There also exists a walk $w-w_2-w_3-\dots -w_{m-1}-v$.

Hence there is a walk.

$u-u_2-u_3-u_{n-1}-v-w_{m-1}-\dots -w_2-w_1$

Hence there exists a path between $u$ and $w$ by previous result. Hence $G$ is connected.

Theorem

Let $G_1$ be isomorphic to $G_2$. Then $G_1$ is connected if and only if $G_2$ is connected.

Definition

Let $G$ be a graph. We say $G$ is disconnected if it is not connected.

Example $1$-regular graph on $6$ vertices

Notice, both of the two graphs below are disconnected. But one is more disconnected than the other.

Definition

We say a subgraph $H$ is a component of $G$ if

1. $H$ is connected

2. $H$ is a subgraph of $G$

3. If $H_2$ contains $H$ as a proper subgraph, then $H_2$ is disconnected.

Example

Consider

is not a component as it is not connected.

is not a component because it is a proper subgraph of the connected subgraph.

In this case the two components are

The number of components measures how disconnected a graph is.

Theorem

Let $G_1$ be isomorphic to $G_2$. Then $G_1$ has the same number of components as $G_2$.

Recall

$H$ is a proper subgraph of $G$ if $H$ is a subgraph and either $V(H)\ne V(G)$ or $E(H)\ne E(G)$.

Definition

Let $X\subseteq V(G)$. We define a cut induced by $X$ as the set of edges with one end in $X$ and one end outside of $X$.

Example

Let $X=\{1,2,3\}$ for the graph

The edges in pink are those induced by the cut $X=\{1,2,3\}$

Example

Find a non-empty, proper set $X\subseteq V(G)$ such that the cut induced by $X$ is empty.

Notice the cut induced by $\{1,2,3\}$ is empty. We could have alternatively used $\{a,b,c\}$ to get a similar result.

Example

Can we find a proper non-empty set $X\subseteq V(G)$ such that the cut induced by $X$ is empty?

Assume $1\in X$. (If $1\notin X$, a similar argument holds). As $(1,2)\in E(G)$, and we want the cut to be empty, we must have $2\in X$.

Similarly, $3\in X$ as $(1,3)\in E(G)$. Similarly, $4,5,6$ and $7$ are all in $X$. Hence $X$ is not a proper subset of $V(G)$.

If we instead assumed $1\notin X$, we could show $2,3,4,5,6$ and $7$ are not in $X$, hence $X$ would be empty.

Recall

Definition

Let $X\subseteq V(G)$. We say that the cut induced by $X$ is the set of edges $(v_1,v_2)\in E(G)$ such that $v_1\in X$ and $v_2\in V(G)\setminus X$.

Theorem

A graph is disconnected if and only if there exists a non-empty proper $X\subseteq V(G)$ such that the cut induced by $X$ is empty.

Note: Proper means $X\subseteq V(G)$ and $X\ne V(G)$ (strict subset).

Proof

Assume $G_1$ is disconnected.

Hence there exists $x,y\in V(G)$ such that there is no path between $x$ and $y$.

Let $X$ be the set of vertices connected to $x$ by a path. We see $x\in X$, hence $X$ is non-empty. Further, $y\ne X$, hence it is proper.

Consider $(v_1,v_2)$ in the cut induced by $X$. Assume $v_1\in X$, $v_2\notin X$. Assume $v_1\in X$, $v_2\notin X$. There is a path from $x$ to $v_1$ and from $v_1$ to $v_2$, hence from $x$ to $v_2$, a contradiction. The cut induced by $X$ is empty.

Assume for the other direction there exists a non-empty proper $X$ such that the cut induced by $X$ is empty.

There exists $x\in X$ and $y\notin X$. We want to show there is no path between $x$ and $y$. Assume for contradiction that $x-v_1-v_2-\dots -v_n-y$ is such a path.

Let $k$ be the maximal term such that $v_k\in X$, $v_{k+1}\notin X$. (Let $x=v_0,y=v_{n+1}$). Then ($v_k,v_{k+1}$) is an edge in the cut induced by $X$, which is supposed to be empty.

Euler Tours

Eulerian Circuits

Example (Königsberg, $18^{\text{th}}$ century)

Question

Can we take a walk from your house, crossing every bridge exactly once, and end up back at your house?

We can translate this question to a graph, and walk on a graph.

Question (Revised)

Does there exist a walk starting and ending at the same vertex that goes through every edge exactly once.

This is not possible (for this graph).

We see every time such a walk goes through a vertex, it must enter and exit via different edges. Hence if it is visited $k$ times, the vertex has degree $2k$.

That is, every vertex has even degree.

In this case, $\mathrm{deg}(A)=\mathrm{deg}(C)=\mathrm{deg}(D)=3$ and $\mathrm{deg}(B)=5$. None of these have even degree.

Hence such a walk does not exist for this graph.

Definition

An Eulerian Circuit is a walk that starts and ends at the same vertex and goes through every edge exactly once.

Definition

An Eulerian walk is a walk that goes through every edge exactly once. This means start and end at different locations.

Example: Modern day Kaliningrad

$B-A-D-B-C-D$ is an Eulerian walk.

Question

Is it always possible to find an Eulerian circuit if all vertices have even degree?

Answer

If $G$ is disconnected, no. If $G$ is connected, then yes. We prove this by induction.

Theorem

Let $G$ be a connected graph such that every vertex has even degree. Then $G$ has an Eulerian Circuit.

Note: This proof also works for multiedges and loops.

Proof

We will do this by induction on the number of edges in the graph

Cases

Assume the statement is true for every connected graph with ($m$ or fewer)$-$edges.

Notice, every vertex has degree at least $2$.

Hence $G$ will have a cycle

$$\begin{array}{r}{v}_1-v_2-\dots -v_{n-1}-v_1\end{array}$$

We remove this cycle from the edge set of the graph.

Every vertex will have even degree. Every component will have $m$ or fewer edges. Hence every component has an Eulerian circuit. Further, every component shares a vertex with the cycle. We now glue things together.

I.e. component with circuit $v_i-w_1-w_2-\dots -w_m-v_i$

We stick this in as $v_1-v_2-\dots -v_3-w_1-\dots -w_m-v_i-v_{i+1}$

Eulerian Circuits

Recall

An Eulerian circuit is a walk starting and ending at the same vertex and using every edge exactly once.

We showed that if $G$ was connected and all vertices had an even degree, then $G$ had an Eulerian circuit

Example

Step 1

Find a cycle.

For example $1-2-3-6-5-4-1$

Step 2

Remove this cycle from the graph to get a number of components.

Repeat arguments on components to get the two cycles.

$$\begin{array}{rl}& 1-2-3-6-5-4-1\\ & 1-2-6-5-2-3-6-5-4-4-1\end{array}$$

Note

A similar proof works for Eulerian Paths. A $45$ bridge version exists in Bristol.

Bridges / Cut-edges

Definition

An edge is a bridge (or cut edge) if removing this edge produces a graph with moire components.

Example

The edge $(2,6)$ is a bridge. After removing this edge we get two components.

The edge $(4,8)$ is also a bridge.

Theorem

If $e$ is a bridge of a connected graph $G$, then $G\setminus \{e\}$ has two components.

The two components will be the set of vertices in $G\setminus \{(v,w)\}$ connected to $v$, say $V$. Similarly for $u$, say $U$.

(Here “connected to” means there exists a path from $u$ to this vertex).

If $x\in V$ then there is no path from $v$ to $x$ in $G\setminus \{e\}$.

There is a path from $v$ to $x$ in $G$.

This means the path goes through the edge $(v,x)$. Hence there is a path from $u$ to $x$.

Hence for any vertex $x$, if $x\notin V$, then $x\in U$, and if $x\notin U$, then $x\in V$.

Hence $G\setminus \{(v,u)\}$ has two components.

Example

Notice that an edge in the previous graph is either contained in a cycle, or a bridge, but not both.

Theorem

An edge is a bridge if and only if it is not in a cycle.

Equivalently

Theorem

An edge is not a bridge if and only if it is not contained in a cycle.

Proof

Let $(v,w)$ be in a cycle, say

$$\begin{array}{r}v-u-u_2-u_3-\dots -u_n-v\end{array}$$

removing $(v,u)$ leaves a graph where $v$ has a path to $u$.

This gives, the set of vertices with a path to $v$ is the same set as the set of vertices with a path to $u$. Hence we have the same number of components.

Assume next that $(u,v)$ is not a bridge. If we remove this edge, we still have a path from $u$ to $v$, say

$$\begin{array}{r}{u}_1-u_2-\dots -u_n-v\end{array}$$

This gives that

$$\begin{array}{r}u-u_2-u_3-\dots -u_n-v-u\end{array}$$

is a cycle in $G$.

Theorem

If there exists two distinct paths from $u$ to $v$, then the graph contains a cycle.

Example

This has two distinct paths from $1$ to $6$. Namely,

$$\begin{array}{r}1-2-3-5-6\\ 1-2-4-5-6\end{array}$$

Notice if we remove the edge $(2,3)$ that there exists a walk from $2$ to $3$. We go

$$\begin{array}{r}2-1-2-4-5-6-5-3\end{array}$$

Hence there exists a path from $2$ to $3$ without the edge $(2,3)$. This is $2-4-5-3$.

Adding the edge back in gives a cycle $2-4-5-3-2$

How could we prove this in general?

Theorem

If there exists two different paths from $u$ to $v$, then $G$ has a cycle.

Proof

Take an edge that is in one path but not in the other.

If we remove this edge, then we still have the same number of components. Hence this edge is not a bridge. Hence this graph has a cycle.

Trees

Trees and Minimally Connected Graphs

Definition

A graph is a tree if it contains no cycle and it is connected.

Example

Definition

We call this graph a forest if every component is a tree.

Definition

Let $T$ be a tree. A vertex $v\in V(T)$ is a leaf if it has degree $1$.

Example

A $1-$regular graph is a forest, and every vertex is a leaf.

Theorem

Let $T$ be a tree. Then there is a unique path from $u$ to $v$ for all $u,v\in V(T)$.

Proof

Our tree is connected, hence there is a path. If there existed two distinct paths, then $T$ would have a cycle. Trees have no cycles. Hence the path is unique.

Theorem

Let $T$ be a tree. Then every edge is a bridge.

Proof

If we had an edge that was not a bridge, then it is in a cycle. Trees have no cycles. Hence every edge is a bridge.

Note This is also true for forests.

Question: What is the relationship between $|V(T)|$ and $|E(T)|$

Example ($G_1,G_2,G_3$ respectively).

	$G_1$	$G_2$	$G_3$
$\Vert V(T)\Vert$	$5$	$4$	$7$
$\Vert E(T)\Vert$	$4$	$3$	$6$

Theorem

Let $T$ be a tree. Then $|E(T)|=|V(T)|-1$

Proof

We will use induction on the number of vertices.

Base Case

$1-$vertex $⟹0$ edges

$2-$vertices $⟹1$ edge

Inductive Hypothesis

Assume this is true for all trees with $m$ or fewer vertices.

Inductive Step

Let $T$ be a tree with $m+1$ vertices. As $T$ is connected, there is a path from every $u$ to $v$, and hence there is an edge. This edge is a bridge.

If we remove this bridge, we have two components, each a tree, and each with $m$ or fewer vertices.

Let the first component be a tree with $s$ vertices, and the seconds have $t$ vertices. We have $s,t\le m$ and $s+t=m+1$

By induction, the first tree has $s-1$ edges. The second has $t-1$ edges. This gives us that the original tree with $m+1$ vertices has

$$\begin{array}{r}\underset{\text{first tree}}{\underbrace{(s-1)}}+\underset{\text{second tree}}{\underbrace{(t-1)}}+\underset{\text{bridge}}{\underbrace{1}}=s+t-1=m\end{array}$$

Example

This gives $10$ vertices in total and $4+4+1=9$ edges.

How many leaves does a tree have?

Question

Can a tree with $p$ vertices have fewer than 2 leaves, or more than $p-1$ leaves?

Theorem

Let $T$ be a tree. Then $t$ has at least 2 leaves. (We assume $|V(T)|\ge 2$).

Proof

By induction

Base Case

$2-$vertices $⟹2$ leaves

Both vertices are leaves. $T$ has $2$ leaves.

Inductive Hypothesis

Assume this is true for every tree with $m$ or fewer vertices.

Inductive Step

Let $T$ be a tree with $m+1$ vertices. This tree will have an edge and this edge is a bridge.

Call this edge $(u,v)$. Let the two trees that result from removing this bridge be $U$ and $V$.

We have two cases.

We could have $u$ is a leaf, and $v$ is not (or equivalently, $v$ is a leaf, $u$ is not) or both vertices are not leaves of $T$.

Case 1:

$u$ is a leaf of $T$, $v$ is not. Hence by induction $V$ will have two leaves. It is possible one of these is $v$. One of these is not $v$, call it $w$.

We can check that $u$ and $w$ are leaves of $T$.

Case 2:

Neither $u$ and $v$ are leaves.

As before, $U$ and $V$ will have two leaves. At least on of the leaves of $U$ is not $u$, call this $x$.

At least one of the leaves of $U$ is not $v$, call this $w$. Then $x$ and $w$ are leaves of $T$.

Spanning Trees

Recall

Definition

We say a subgraph $H$ of $G$ is a spanning subgraph if $V(H)-V(G)$.

Definition

We say $G$ is a tree if it contains no cycles and is connected.

Definition

We say $T$ is a spanning tree of $G$ if $T$ is a spanning subgraph of $G$ and it is a tree.

Example

Find a spanning tree of

Example

Does a $1-$regular graph on $4$ vertices have a spanning tree?

No We cannot find an edge from the left two vertices to the right two vertices. There are no spanning subgraphs, hence no spanning trees.

Theorem

A graph $G$ has a spanning tree if and only if $G$ is connected.

Proof

Assume first that $G$ has a spanning tree, say $T$.

Take any two vertices in $G$, say $u$ and $v$. Then $u,v\in V(T)$ as $T$ is a spanning subgraph.

As $T$ is a tree, there exists a (unique) path from $u$ to $v$. This path uses edges in $E(G)$. Hence there exists a path from $u$ to $v$ in $G$. This proves $G$ is connected.

Assume for the other direction that $G$ is connected.

$E(G)$ will contain some edges that are bridges, and some that are not. We will construct our spanning tree by removing non-bridge edges.

Create a subgraph of $G$ by removing an edge that is not a bridge. If no such edge exists, we have a tree. Repeat this process on this new subgraph as needed.

1. We never remove a vertex, so all of these subgraphs are spanning.

2. We never remove a bridge, hence all of these subgraphs are connected.

3. At some point this process will step (I.e. when $|E(H)|=|V(H)|-1$)

The result after repeating this will be a spanning connected subgraph where every edge is a bridge. I.e., a spanning tree.

Example

Find a spanning tree of the $4\times 4$ graph

Method 2 - Grow the tree

Start with any vertex. This will be our starting (non-spanning) tree.

Find any edge from inside this tree to outside this tree. Add this edge to get a larger tree. Repeat as necessary until you have every vertex.

Example Same as before

Characterizing Bipartite Graphs

Recall a graph $G$ is bipartite if there exists $A,B\subseteq V(G)$ where

1. $V(G)=A\cup B$

2. $A\cap B=\varnothing$

3. Every edge ($u,v$) has one end in $A$ and one end in $B$.

Theorem

A cycle of odd length is not bipartite.

Proof

Assume the graph is bipartite.

Let $v$ be a vertex. Assume without loss of generality that $v\in A$.

The two adjacent vertices to $v$ are in $B$.

The vertices adjacent to the vertices adjacent to $v$ are in $A$. (I.e. the vertices with a path of length 2 from $v$).

Continue this process. Vertices with a path of length $1,3,5,\dots$ are in $B$ and length $0,2,4,6,\dots$ are in $A$.

This is where the problem occurs, as there is a path of odd length from $v$ to $v$, hence it is in both $B$ and $A$.

Hence the cycle is not bipartite.

Corollary

If $G$ contains a cycle of odd length, then it is not bipartite.

Example

Proof

The subgraph of a bipartite graph is bipartite. A cycle of odd length is not bipartite.

Theorem

A graph is bipartite if and only if it does not contain a cycle of odd length.

Equivalently

Theorem

A graph is not bipartite if and only if it contains a cycle of odd length.

Proof

Assume without loss of generality that $G$ is connected. We have already shown that if $G$ has a cycle of odd length, then it is not bipartite or equivalently, if it is bipartite, then it will not contain a cycle of odd length.

We will show that if $G$ is not bipartite then it will contain a cycle of odd length.

Let $G$ be a connected graph that is not bipartite. As $G$ is connected it has a spanning tree $T$. All trees are bipartite. Hence we can divide the vertices of $V(T)$ into two sets $A$ and $B$ such that all edges in $T$ have one end in $A$ and one end in $B$.

As $G$ is not bipartite, there exists some edge $(u,v)\in E(G)$ such that either $u,v\in A$ or $u,v\in B$.

We see $(u,v)\notin E(T)$, (as $T$ is bipartite). There is a path from $u$ to $v$ in $T$, because $T$ is a tree. Further this path is even length.

Connecting $(u,v)$ to this path gives a cycle of odd length, which proves this result.

To see the path is even length, we see the path is of the form

$$\begin{array}{r}u-u_1-u_2-u_3-\dots -u_{n-1}-v\end{array}$$

Assume $u,v\in A$ (same argument works if they are in $B$).

$$\begin{array}{r}\underset{A}{\underbrace{u}}-\underset{B}{\underbrace{u_1}}-\underset{A}{\underbrace{u_2}}-\underset{B}{\underbrace{u_3}}-\underset{A}{\underbrace{u_4}}-\dots -\underset{A}{\underbrace{v}}\end{array}$$

Distance from A’s is even.

Example

Step 1- Find spanning tree

Step 2 - Make spanning tree bipartite

Find an edge in $E(G)$ that has both ends in $A$ or both ends in $B$.

At this point we construct an odd length cycle.

Planar Graphs

Planarity

Definition

We say a graph is planar if we can draw the graph such that no edges cross.

Example

${\mathcal{K}}_4$ - complete graph on 4 vertices.

This gives us two planar embedding of ${\mathcal{K}}_4$. Hence ${\mathcal{K}}_4$ is planar.

Example

(Not proven yet) ${\mathcal{K}}_5$ does not have a planar embedding.

Definition

A planar embedding is a diagram where none of the edges cross.

Definition

Let $G$ have a planar embedding. Then we say a face of the embedding is a region “contained” by the graph.

Example

Consider the embedding of ${\mathcal{K}}_4$

This embedding has $4$ vertices, $6$ edges and $4$ faces.

Example

Let $T$ be a tree.

Then $T$ is planar and has a planar embedding

$1$ face, $5$ vertices, $4$ edges

Example

Let $G$ be a connected $2$-regular graph. $G$ is planar and has two faces.

Fact

If $G$ is isomorphic to $H$, then $G$ is planar if and only if $H$ is planar.

Fact

If $H$ is a subgraph of a planar graph $G$, then $H$ is planar.

Definition

We say two faces are adjacent if they share an edge.

Definition

Let $u_1-\dots -u_n$ be a minimal walk containing a face and which visits every vertex touching the face. The length of this walk is the degree of the face.

Example - ${\mathcal{K}}_4$

$\mathrm{deg}(f_2)=3$ given by

Similarly, $\mathrm{deg}(f_2)=\mathrm{deg}(f_3)=\mathrm{deg}(f_4)=3$

Example

$\mathrm{deg}(f_2)=3$ given by the walk $A-B-C-A$

The walk for $f_1$ is $A-B-C-D-C-A$. That gives $\mathrm{deg}(f_1)=5$.

For ${\mathcal{K}}_4$, $\sum \mathrm{deg}(f)=3+3+3+3=12$

Notice ${\mathcal{K}}_4$ has $6$ edges.

For

$\sum \mathrm{deg}(f)=3+5=8$

This had $4$ edges.

Theorem

$$\begin{array}{r}\sum \mathrm{deg}(f)=2|E(G)|\end{array}$$

Proof

When we add the degree of the faces, we count every edge twice. One for each side of the edge.

This is known as the handshaking lemma for faces. It is very similar to the formula $\sum \mathrm{deg}(v)=2|E(G)|$ for the degree of each vertex.

Euler’s Formula

Consider a connected graph with $4$ vertices. What is the relation between the number of faces and number of edges.

$4$ vertices, $3$ edges, $1$ face

Case 2

$4$ vertices, $4$ edges, $2$ face

Case 3

$4$ vertices, $5$ edges, $3$ face

Case 4

Observation: When we increase the number of edges, we increase the number of faces.

Consider instead what happens if we leave the number of edges the same, and increase the number of vertices.

	$G_1$	$G_2$	$G_3$	$G_4$
# edges	$6$	$6$	$6$	$6$
# vertices	$4$	$5$	$6$	$7$
# faces	$4$	$3$	$2$	$1$

Observation: If we increase the number of vertices, we decrease the number of faces.

Guess

Let $p=|V(G)|,q=|E(G)|,f=\#$ faces. We can guess

$$\begin{array}{r}f-q+p=2\end{array}$$

Test

$p=9,q=12,f=5$

Euler’s Formula

Theorem (Euler)

Let $G$ be a planar connected graph with $p$ vertices, $q$ edges and $f$ faces. Then $p+f-q=2$

Proof

We will prove this by induction on the number of edges.

Let $G$ have $p-$vertices. The graph with a minimal number of edges that is connected is a tree. A tree has $q=p-1$ edges. The only face of this planar graph is the outside face, hence $f=1$.

This gives $p+f-q=p+1-(p-1)=p+1-p+1=2$

Hence Euler’s Formula holds for a tree.

Assume Euler’s formula holds for all $p-1\le q\le Q$, and a graph with $Q+1$ edges is planar.

Notice $G$ is not a tree. Hence there will contain an edge that is not a bridge.

The face on either side of this not bridge will be different faces. Remove this edge to get a new graph with $q^{\prime }=q-1$ edges, $p^{\prime }=p$ vertices and $f^{\prime }=f-1$ faces in this new graph. By induction

$$\begin{array}{r}{f}^{\prime }+p^{\prime }-q^{\prime }=2\end{array}$$

This implies

$$\begin{array}{r}(f-1)+(p)-(q-1)=2⟹f+p-q=2\text{as required}\end{array}$$

Example

$q=7,p=5,f=4$

$q=5,p=5,f=3$

$q=5,p=5,f=2$

$q=4,p=5,f=1$

Question

Is the # of cycles in a graph related to the number of faces?

Answer: Not in an obvious way, so probably no.

Question

Can we find a planar graph where $\mathrm{deg}(v)=3$ for all $v$, and $\mathrm{deg}(f)=3$ for all $f$? If so, what does it look like?

We know

$$\begin{array}{rl}\sum \mathrm{deg}(v)& =2|E(G)|\\ \sum \mathrm{deg}(f)& =2|E(G)|\\ |V(G)|+|F(G)|& -|E(G)|=2\end{array}$$

Let $p=|V(G)|,q=|E(G)|,f=|F(G)|$

First equation gives: $3\cdot p=2q⟹p=\frac{2}{3}\cdot q$

Second equation gives: $3\cdot f=2q⟹f=\frac{2}{3}\cdot q$

Using this information in Euler’s formula gives

$$\begin{array}{r}2=p+f-q=\frac{2}{3}\cdot q+\frac{2}{3}\cdot q-q=\frac{1}{3}q⟹q=6\end{array}$$

If such a graph exists, it has $6$ edges, $4$ vertices and $4$ faces.

Every face and vertex has degree $3$.

This is an example of a platonic solid.

Platonic Solids

Definition

A graph $G$ is a platonic solid if

1. It is connected and planar

2. All vertices have the same degree

3. All faces have the same degree

Example

We showed ${\mathcal{K}}_4$ is a platonic solid where all vertices have degree $3$ and all faces have degree $3$.

Theorem

There are only $5$ platonic solids.

Proof

Assume $\mathrm{deg}(f)=d_f$ and $\mathrm{deg}(v)=d_v$ for every vertex $v$ and face $f$.

Let the platonic solid have $p-$vertices, $q-$edges and $f$ faces.

By the Handshake Lemma for vertices we have

$$\begin{array}{r}2q=\sum _{v\in V(G)}\mathrm{deg}(v)=\sum _{v\in V(G)}{d}_v=p\cdot d_v\end{array}$$

Using Handshake Lemma for faces gives

$$\begin{array}{r}2q=f\cdot d_f\end{array}$$

This gives $p=\frac{2}{d_v}\cdot q$, $f=\frac{2}{d_f}\cdot q$.

By Euler’s formula we have $p+f-q=2$.

This gives

$$\begin{array}{r}\left(\frac{2}{d_v}\cdot q+\frac{2}{d_f}\cdot q-q\right)=2\\ q\left(\underset{\text{must be positive}}{\underbrace{\frac{2}{d_v}+\frac{2}{d_f}-1}}\right)=2\end{array}$$

We must have $\frac{2}{d_v}+\frac{2}{d_f}-1>0$

We notice $d_f\ge 3$, and similarly $d_v\ge 3$ (see note).

Note: We should have added the assumption that $\mathrm{deg}(v)\ge 3$ for every vertex in the definition of a platonic solid.

Case 1

$d_v=3,d_f=3$

$$\begin{array}{r}q\left(\frac{2}{3}+\frac{2}{3}-1\right)=q\left(\frac{1}{3}\right)=2⟹q=6\end{array}$$

We see that if $d_v\ge 6$, and $d_f\ge 3$, then

$$\begin{array}{r}\frac{2}{d_v}+\frac{2}{d_f}-1\le \frac{2}{6}+\frac{2}{3}-1=0\end{array}$$

Hence we may assume $3\le d_v\le 5$.

Similarly we may assume $3\le d_f\le 5$.

$d_v$	$d_f$	$\frac{2}{d_v}+\frac{2}{d_f}-1$	$q$	$p$	$f$
$3$	$3$	$\frac{1}{3}$	$6$	$4$	$4$
$3$	$4$	$\frac{1}{6}$	$12$	$8$	$6$
$4$	$3$	$\frac{1}{6}$	$12$	$6$	$8$
$4$	$4$	$0$	$-$	$-$	$-$
$3$	$5$	$\frac{1}{15}$	$30$	$12$	$20$
$5$	$3$	$\frac{1}{15}$	$30$	$20$	$12$
$4$	$5$	$<0$	$-$	$-$	$-$
$5$	$4$	$<0$	$-$	$-$	$-$
$5$	$5$	$<0$	$-$	$-$	$-$

$d_v=3,d_f=3$

$d_v=3,d_f=4$

$d_v=4,d_f=3$

$d_v=5,d_f=3$

dodecahedron

$d_v=3,d_f=5$

icosahedron

Fact

The planar dual of a Platonic solid is a platonic solid.

Non-Planar Graphs

Theorem

${\mathcal{K}}_5$ is not a planar graph.

Proof

Assume that it is planar and derive a contradiction.

We see $p=|V(G)|=5,q=|E(G)|=10$

$$\begin{array}{r}f+p-1=f+5-10=2⟹f=7\end{array}$$

If ${\mathcal{K}}_5$ is planar, then it would have $5$ vertices, $10$ edges, and $7$ faces.

We see $\mathrm{deg}(f)\ge 3$ for all faces.

Hence by the handshaking lemma for faces, we have

$$\begin{array}{r}20=2q=\sum _{f_i}\mathrm{deg}(f_i)\ge \sum _{i=1}^{7}3=21\end{array}$$

This gives $20\ge 21$, which is a contradiction.

Hence ${\mathcal{K}}_5$ is not planar.

Theorem

${\mathcal{K}}_{3,3}$, the complete bipartite graph with $|A|=|B|$, is not planar.

Proof

Assume that ${\mathcal{K}}_{3,3}$ is planar. This graph has $p=6$ vertices and $q=9$ edges. By Euler’s formula, $p+f-q=2$, this gives us $f=5$ faces.

Because ${\mathcal{K}}_{3,3}$ is bipartite, all cycles (and hence all faces) have an even length (degree). Hence we have $\mathrm{deg}(f_i)\ge 4$ for $i=1,2,\dots ,5$

By the handshaking lemma for faces,

$$\begin{array}{r}2\cdot q=18\sum _{i=1}^5\mathrm{deg}(f_i)\ge \sum _{i=1}^{5}4=20\end{array}$$

This is a contradiction. Hence ${\mathcal{K}}_{3,3}$ is not planar.

Theorem

Let $G$ be a connected planar graph with $p$ vertices and $q$ edges. Then $q\le 3p-6$

Proof

Assume $G$ is a connected planar graph. We know $p+f-q=2$. We further know that $\mathrm{deg}(f)\ge 3$ for all faces.

By Handshake Lemma

$$\begin{array}{r}2q=\sum _i\mathrm{deg}(f_i)\ge 3\cdot f\end{array}$$

This gives $3p+3f-3q=6$

$$\begin{array}{rl}& ⟹3p+2q-3q\ge 6\\ & ⟹3p-6\ge p,\text{as required}\end{array}$$

What about a face of degree 2?

It is worth noting that the only connected planar graph (without loops or multiple edges) that has a face of degree $2$ is.

”I always ignore this special case because I forget it exists” - Kevin.

This has $p=2,q=1$.

$1=q\le 3p-6=0$

So the theorem doesn’t hold for the degenerate case.

Theorem

Let $G$ be a planar graph. Then there exists a vertex $v\in V(G)$ such that $\mathrm{deg}(v)\le 5$.

Proof

Assume $G$ is a non-degenerate planar graph. If every vertex had $\mathrm{deg}(v)\ge 6$, then

$$\begin{array}{r}2\cdot q=\sum \mathrm{deg}(v_i)\ge 6\cdot p\end{array}$$

Hence $3p\le q\le 3p-6$, a contradiction.

Kuratowski’s Theorem

Definition

An edge subdivision of a graph is done by replacing an edge with a path of length $\ge 1$.

Example

Fact

Let $G_2$ be an edge subdivision of $G_1$. Then $G_1$ is planar if and only if $G_2$ is planar.

Fact

Let $H$ be a subgraph of $G$. If $G$ is planar, then $H$ is planar. If $H$ is non-planar then $G$ is non-planar.

Warning

If $H$ is planar, we can assume nothing about $G$.

Let $G={\mathcal{K}}_3$

Theorem (Kuratowski)

A connected graph is not planar if and only if it contains a subgraph that is an edge subdivision of ${\mathcal{K}}_5$ or ${\mathcal{K}}_{3,3}$.

Proof

We see an edge subdivision of ${\mathcal{K}}_{3,3}$ and ${\mathcal{K}}_5$ are non-planar. Hence if this is a subgraph, the original graph is non-planar.

The other direction is beyond the scope of the course.

Example

${\mathcal{K}}_6$ is not planar.

To see this, if we remove a single vertex and all edges attached to it, we get the subgraph ${\mathcal{K}}_5$.

Example

Consider the $GHMS-$graph on vertices $\{1,2,3,4,5,6,7\}$.

This is non-planar.

This has a ${\mathcal{K}}_{3,3}$ as a subgraph.

Hence this is non-planar.

Colouring and Planar Graphs

Definition

Let $G$ be a graph. A $k-$colouring (of the vertices) is a map from $V(G)$ to a set of size $k$ such that adjacent vertices are assigned different values.

Example

This graph does not have $2-$colouring.

Fact

A graph is $1-$colourable if and only if it is $0-$regular (i.e. no edges).

Fact

A graph is $2-$colourable if and only if it is bipartite.

(Colour $A$ one colour, and everything in $B$ another colour).

Example

A cycle of odd length is $3-$colourable

Example

Consider a planar graph.

In general, every planar graph can be $4-$coloured.

One way to think of this problem is to colour different countries different colours such that if two countries share a border, they are different colours.

The world map is (probably not) a planar map.

Borders of France

Country	Border Length
Brazil	$730$ km
Spain	$646$ km
Belgium	$556$ km
Suriname	$556$ km
Switzerland	$525$ km
Italy	$476$ km
Germany	$418$ km

Theorem

Let $G$ be a planar graph. Then $G$ is $6-$colourable.

Proof

We prove this by induction.

This is clearly true if $G$ has less than or equal to $6$ vertices. Assume this is true for up to $p\ge 6$ vertices, and let $G$ be the planar map with $p+1$ vertices.

As $G$ is a planar graph, there exists a vertex of degree at most $5$, say $v$.

Let $G^{\prime }$ be the graph where we remove $v$ and all edges to $v$.

Then $G^{\prime }$ is a planar graph with $p$ vertices. By induction it is $6$ colourable. Colour it.

Apply this colouring to the original graph. We have $6-$choices to colour $v$, and $5-$neighbours that restrict this choice.

Colour $v$ anything that its neighbours are not.

This gives a $6-$colouring of $G$.

Theorem

Let $G$ be a planar graph. Then $G$ is $5-$colourable.

Proof

As before, we prove by induction. This is true for all $G$ with $5$ or fewer vertices. Assume true for graphs with $p\ge 5$ vertices, and let $G$ be a planar graph with $p+1$ vertices.

As $G$ is a planar graph, there exists a vertex $v$ with $\mathrm{deg}(v)\le 5$. Choose this vertex.

Case 1 $\mathrm{deg}(v)\le 4$

As before, we remove $v$ and all edges to $v$, colour the new graph. Then use this colouring for $G$, choosing any colour for $v$ that it is not adjacent to (we have options).

Case 2 $\mathrm{deg}(v)=5$

Let its neighbours be labeled $A,B,C,D,E$.

Consider the subgraph on $A,B,C,D,E$ and all edges from $G$.

This subgraph is not ${\mathcal{K}}_5$ (As ${\mathcal{K}}_5$ is not planar). This gives that at least two vertices do not have an edge between them. Say $A$ and $B$.

Construct a new graph $G^{\prime }$ where we remove $A,B$ and $v$, and add a new vertex $AB$. If $(u,v)\in E(G)$ with $v=A$ or $v=B$ then $(u,AB)\in E(G^{\prime })$.

This new graph is a planar graph. Hence by induction it has a $5-$colouring. Colour it.

Take this colouring to colour the original graph.

We colour both $A$ and $B$ the colour assigned to $AB$ (there is no edge between them).

We colour $v$ to be anything $A,B,C,D,E$ is not (of which there are at most $4$ restrictions).

Theorem

Every planar graph is $4-$colourable.

Step 1

Assume every face is a triangle.

Step 2

Break this into $633$ cases.

Step 3

Ask a computer for help.

Step 4

Defend yourself from mathematicians that hate computers.

Matchings

Matching

Definition

Let $G$ be a graph. A matching $M$ is a $1-$regular subgraph of $G$. Alternatively, $M$ is a collection of edges such that every vertex is incident to at most one edge.

Example

${\mathcal{K}}_6$

The matching is given by $(1,6),(2,5),(3,4)$. Every vertex is saturated.

Example

${\mathcal{K}}_6$ (again)

The single edge $(3,6)$ is a (non-maximal) matching

$3$ and $6$ are saturated, $1,2,4,5$ are unsaturated.

Definition

We say a vertex $v$ is saturated by a matching $M$ if it is incident to an edge in $M$. Otherwise it is unsaturated.

Recall

For an edge $(u,v)$, we say both $u$ and $v$ are incident to $(u,v)$.

Definition

We say a matching is perfect if every vertex is structured.

The first example is perfect, the second example is not.

Example

${\mathcal{K}}_5$ does not have a perfect matching. We see this because ${\mathcal{K}}_5$ has an odd number of vertices.

Example

The graph below does not have a perfect matching.

Example

Let $G$ be a bipartite graph with partition $A$ and $B$. If $G$ has a perfect matching then $|A|=|B|$.

Proof

To see this, we see that every edge in $M$ is incident to one vertex in $A$ and one in $B$. So,

$$\begin{array}{r}|A|=|B|=|M|\end{array}$$

Definition

Let $G$ be a graph with a matching $M$. We say a path in $G$ is an alternating path if adjacent edges in the path have one edge in $M$ and one edge not in $M$.

Example

This matching is not a perfect matching (as both $b$ and $h$ are unsaturated). Some alternating paths include

$$\begin{array}{rl}& a-e-b\\ & b-g-d\\ & h-c-f-a-e-b\\ & c-f\end{array}$$

These paths could be odd or even length, starting or ending with edges in $M$ or not in $M$.

Definition

We say an alternating path is augmenting if it starts and ends at an unsaturated vertex.

Example

This has a (non-perfect) matching $(a,c)$.

It has an augmenting path $B-A-C-D$. We can construct a new (larger) matching by removing from $M$ every edge in $M$ and in the path, and add every edge not in $M$ and in the path.

This gives a larger matching.

Definition

We say a matching is maximal if there are no larger matchings.

Example

This matching is maximal, but not perfect.

Fact

If there exists a perfect matching, then the perfect matching is maximal.

Theorem

A matching $M$ is maximal if and only if there is no augmenting path.

Equivalently,

A matching is not maximal if and only if there exists an augmenting path.

Algorithm to find maximal matching

1. Find an augmented path

2. Augment matching and repeat until we can’t find an augmenting path.

Example

This is a maximal matching.

Proof

Assume there exists an augmenting path. This allows us to create a larger matching using the augmenting path. Hence $M$ was not maximal.

Assume $M$ is a matching that is not maximal. Let $M^{\prime }$ be a larger matching. Consider $(M\setminus M^{\prime })\cup (M^{\prime }\setminus M)$.

In this case, the path corresponds to an augmenting path in $M$.

This construction creates a number of paths that are all alternating paths. At least one of these paths will be augmenting (Not advice, but worth thinking about).

Covers

Definition

A cover $C$ is a set of vertices such that every edges has at least one end in $C$.

Example

Both $\{a,b,c,d\}$ and $\{e,f,g,h\}$ are covers.

Lemma

Let $M$ be a matching of $G$ and $C$ be a cover of $G$. Then $|M|\le |C|$.

Proof

For each edge $(u,v)\in M$ we must have either $u\in C$ or $v\in C$. As matchings are disjoint, each edge must contribute to a different $c\in C$. Hence $|M|\le |C|$.

Example

In the above, $(a,c)$, $(b,f)$, $(c,g)$, $(d,h)$ is a matching of size $4$, and $\{a,b,c,d\}$ and $\{e,f,g,h\}$ are covers of size $4$.

This proves $M$ is a maximal matching and $C$ is a minimal cover.

Lemma

If $|M|=|C|$, then $M$ is a maximal matching and $C$ is a minimal cover.

Example

We need not have equality. Consider

Here $|M|\le 1<2\le |C|$ for all covers and all matchings.

It turns out (next topic), that if $G$ is bipartite then we can achieve equality.

König’s Theorem

Theorem

Let $G$ be a bipartite graph, then the size of a maximal matching is equal to the minimal size of a cover.

Before proving this result we will first recall how to find a maximal matching.

Step 1 Find any matching

Step 2 Find an augmenting path and augment

Step 3 Repeat Step $2$ as necessary

Step 4 If we cannot find an augmenting path we are done.

Note

1. Augmenting paths go from unsaturated vertices to unsaturated vertices

2. Augmenting paths are odd length

3. Odd length paths in bipartite graphs have one end in $A$ and one end in $B$.

Example

$U_A=$ unsaturated vertices in $A=\{b,d\}$.

$U_B=$ unsaturated vertices in $B=\{f,h\}$.

$X=$ vertices in $A$ connected to $U_A$ by an alternating path $=\{b,a,c,d\}$

$Y=$ vertices in $B$ connected to $U_A$ by an alternating path $=\{e,f,g,h\}$

Notice $U_B\cap Y=\{f,h\}$ hence there exists an augmenting path (say $f-c-g-d$). We can use this to construct a better matching.

Repeat this process on the new graph

$U_A=\{b\}$

$U_B=\{h\}$

$X=\{b,d\}$

$Y=\{g\}$

Notice $U_B\cap Y=\{\}$, the empty set.

This tells us that $M$ is a maximal matching.

Theorem

Let $M$ be a maximal matching $U_A,U_B,X,Y$ as before.

Let $C=Y\cup (A\setminus X)$. Then $C$ is a cover and $|C|=|M|$.

Looking at the graph from previous example.

Notice we can rearrange the graph in the following way

Observations

1. There are no edges from $X$ to $B\setminus Y$ (proved before)

2. There are no edges in $M$ from $Y$ to $A\setminus X$

3. $|Y|\le |X|$

4. $|A\setminus X|\le |B\setminus Y|$

Proof of 2

Assume there is a matching from $Y$ to $A\setminus X$. Every vertex in $Y$ has an alternating path to $U_A$.

This path starts with an edge not in the matching. Hence any vertex connected to a vertex in $Y$ by a matching has an alternating path to $U_A$. Hence it is in $X$. Hence not in $A\setminus X$.

Proof of 3

Every vertex in $Y$ is connected to a matching (since assuming maximal matching). All of this matching must go to $X$ (as they can’t go to $A\setminus X$). Hence $|Y|\le |X|$.

Proof of 4

A similar argument shows $|A\setminus X|$ is less than or equal to $|B\setminus Y|$.

Every vertex in $A\setminus X$ is connected to $M$ (otherwise in $U_A$)

Hence $|A\setminus X|\le |B\setminus Y|$

Last Part

$|C|=|M|$

We can partition the matching into two parts. Those from $X$ to $Y$ which has size $|Y|$ and those from $A\setminus X$ to $B\setminus Y$ with size $|A\setminus X|$.

Hence, this has the same size as the cover.

Example

$U_A=\{a,b,c\}$

$U_B=\{f,h,i\}$

$X=\{a,b,d,c\}$

$Y=\{h,i,j\}$

path $h-d-j-c$.

$U_A=\{a,b\}$

$U_B=\{f,i\}$

$X=\{ab,c,e\}$

$Y=\{g,h,i,j\}$

path $i-e-j-d-h-b$

$U_A=\{a\}$

$U_B=\{f\}$

$X=\{a,b\}$

$Y=\{h\}$

$U_B\cap Y=\varnothing$

Note on König’s Theorem

• The process of creating $X$ and $Y$ is called the $X-Y$ construction

• The course notes and other sections used $X_0=$ unsaturated vertices.

• We use $U_A$ and $U_B$ for the unsaturated vertices in $A$ and $B$.

I.e. $X_0=U_A\cup U_B$

Applications of König’s Theorem

Theorem (Hall's)

Let $G$ be bipartite, with partitions $A$ and $B$. If $M$ is a matching, then $|M|\le \min (|A|,|B|)$

(Every edge in the matching has one end in $A$ and one end in $B$).

For some graphs, this is a strict inequality.

Question

When do we get equality?

Notation

Let $D\subseteq A$. We define

$$\begin{array}{rl}N(D)& =\{b\in B:(a,b)\in E,a\in D\}\\ & =\text{vertices incident to something in D}\\ & =\text{neighbours of D}\end{array}$$

Example

Theorem

Let $G$ be bipartite (with respect to $A$ and $B$). There exists a matching that saturates every vertex in $A$ if and only if for all $D\subseteq A,|D|\le |N(D)|$.

Example

Notice if $D=X=\{a,b\}$

Then $N(D)=\{h\}=Y$

We have $|D|=2>1=|N(D)|$

As there exists a $D$ with $D>|N(D)|$, there does not exist a matching saturating $X$.

Proof

Assume there exists a matching $M$ which saturates $X$.

Take $D\subseteq A$ to be any subset.

Every vertex $a\in D$ is connected to some edge in the matching.

Every one of these edges is connected to a different vertex in $B$.

Every vertex in $B$ connected to $D$ by a matching in $M$ is in $N(D)$. Hence $|D|\le |N(D)|$.

Example

Proof

Assume that there does not exist a matching which saturates all of $A$. We wish to find a $D$ such that $|D|>|N(D)|$.

Let $M$ be a matching of maximal size. There will be unsaturated vertices in $A$. I.e. $U_A\ne \varnothing$.

Construct $X$ and $Y$ as before. We have $U_A\le X$, have $X\ne \varnothing$.

Take $D=X$.

From Monday, there are no matchings from $Y$ to $A\setminus X$.

Further, there are no edges from $X$ to $B\setminus Y$.

$$\begin{array}{rl}|N(D)|=|Y|& =|C|-|A\setminus X|\\ & <|A|-|A\setminus X|=|X|=|D|\end{array}$$

Perfect Matchings in Bipartite Graphs

Theorem

Let $G$ be a $k-$regular bipartite graph with $k\ge 1$. Then $G$ has a perfect matching.

Recall

A perfect matching is a matching which saturates every vertex.

Observation 1 $|A|=|B|$

We see the number of edges in $k\cdot |A|$ and $k\cdot |B|$. Hence $|A|=|B|$.

Proof

We will show for all $D\subseteq A$ that $|D|\le |N(D)|$, which will prove the result.

Assume for a contradiction that there exists a $D$ with $|N(D)|<|D|$. We count the edges from $D$ to $N(D)$ in two different ways.

We see there are $k\cdot |D|$ edges from $D$ to $N(D)$ (as every vertex has $k$ edges).

We see that we have at most $k\cdot |N(D)|$ edges from $N(D)$ to $D$ (as every vertex has $k$ edges some of which go to $D$).

Hence

$$\begin{array}{rl}k\cdot |D|& =\#\text{of edges from }D\text{ to }N(D)\\ & =\underset{\text{by assumption}}{\underbrace{k\cdot |N(D)|<k\cdot |D|}}\end{array}$$

This is a contradiction. Hence there is a perfect matching.

Example $3-$regular

Edge-Colouring

Definition

Let $G$ be a graph. We say it has a $k$-edge colouring if there is an assignment of $k-$colours to the edges such that edges of the same colour never touch.

I.e. each colour is a matching.

Example

${\mathcal{K}}_5$

This is a $5-$edge colouring of ${\mathcal{K}}_5$

Exercise

Let $G$ be a graph that is $k-$edge-colourable. Then $\mathrm{deg}(v)\le k$ for all $v\in V(G)$.

Note

For any colour, the set of edges of that colour is matching ($1-$regular graph).

Theorem

Let $G$ be bipartite, and let $\Delta ={\max }_{v\in G}\mathrm{deg}(v)$. Then $G$ has a $\Delta -$edge colouring.

Method

1. Find a matching of maximal size that saturates all of $v$ with $\mathrm{deg}(v)=\Delta$.

2. Colour this matching, remote it and repeat.

$\Delta =\max \mathrm{deg}(v)=3$

This includes $\{b,c,g\}$

Find a matching of maximal size that saturates $\{b,c,g\}$.

Remove and repeat.

$\Delta =2$ includes $\{b,c,g\}$.

Remove and repeat.

$\Delta =1$ includes $\{b,c,f,g\}$

Thus we have,

If we can do step $1$, then it is easy to see how step $2$ can be used to find the $\Delta -$edge-colouring.

Proof

Let $\Delta =\max \mathrm{deg}(v)$ and $K=\{v:\mathrm{deg}(v)=\Delta \}$. Let $M$ be a matching that is maximal and saturates the maximal amount of $K$. If this matching saturates $K$ we are done. Assume that there is some vertex in $K$ left unsaturated. We can assume that it is in $A$.

Construct

$U_{A\cap K}=$ unsaturated vertices in $A\cap K$. Non-empty by assumption.

$X=$ vertices with alternating paths to $U_{A\cap K}$ starting in $A$.

$Y=$ vertices with alternating paths to $U_{A\cap K}$ starting in $B$.

Fact

All $v\in X$ have $\mathrm{deg}(v)=\Delta$.

Assume that it is not true. We have an alternating vertex from $v$, starting with an edge in $M$ and ending in $U_{A\cap K}$.

We replace edges in this path so that those in $M$ are not in $M$ and those not in $M$ are now in $M$.

This saturates more things in $K$. A contradiction.

Fact

If $y\in Y$, then there exists $x\in X$ with $(x,y)\in M$.

As this is a maximal matching, all vertices in $y$ are not unsaturated. Hence they are connected to a matching. Further, there are no matchings from $Y$ to $A\setminus X$ (proved earlier). Hence they connect to $X$.

This tells us $|Y|\le |X|$ in size.

Consider the set of edges from $X$ to $Y$.

$$\begin{array}{rlrl}\Delta |Y|& \le \Delta |X|& & \text{as ∣Y∣≤∣X∣}\\ & =\sum _{v\in X}\mathrm{deg}(v)& & \text{as all v∈X has deg(v)=Δ}\\ & \le \sum _{v\in Y}\mathrm{deg}(y)& & \text{includes all edges from Y to X, plus some from Y to A∖X}\\ & \le \Delta \cdot |Y|& & \text{as all vertices have deg(v)≤Δ}\end{array}$$

Hence $\Delta |Y|\le \Delta |X|\le \Delta |Y|$

Hence $|X|=|Y|$

As everything in $Y$ has a matching to connecting in $X$, we get everything in $X$ has a matching. Hence $K$ is saturated.