# Math 239 Formula Theorems It seems Gitbook and Typora don't render markdowns exactly the same, so this looks really messed up. \[Nice PDF here]\( 239 FormulaTheorems.pdf)). ## Enumeration | Sets | **Cartesian Product** | | --------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- | ----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- | |

Unordered: {1, 1, 3} = {1, 3, 1}
Ordered: {1, 1, 3} \ne {1, 3, 1}
$$

| A \cup B | | **Binomial Coefficient Sets** | **Binomial Theorem** | | $$S\_{k,n}={\Omega \subseteq {1, 2, ..., n}: | \Omega | | **Bijection** | **Bijection Theorems** | |

S\rightarrow T
1. f(x\_1)=f(x\_2) \Rightarrow x\_1=x\_2 - 1-1/injective
2. \forall y\in T, \exists x \in S, f(x)=y - onto/surjective

|

Suppose S, T are finite sets and f:S \rightarrow T
(i) If f is 1-1 $$\Rightarrow

| | **Generating Series** | **Generating Series Theorems** | |

S is a set with weight function w:S\rightarrow {0, 1, 2, ...}
\Phi\_s(x)=\sum\limits\_{\sigma \in S}x^{w(s)}

|

\Phi\_s(x)=\sum\limits\_{k\ge 0}a\_kx^k
$$

| | **Formal Power Series** | **FPS Operations** | |

C(x)=c\_0+c\_1x+c\_2x^2+...+\sum\limits\_{k \ge 0}^\infty c\_kx^k
where (c\_0, c\_1, ...) are rational numbers.

\[x^n]C(x) = c\_n - Coefficient of x^n

|

A(x) = \sum\limits\_{k=0}^\infty a\_kx^k, B(x) = \sum\limits\_{k=0}^\infty b\_kx^k
Addition: A(x)+B(x)=\sum\limits\_{k=0}^\infty (a\_k+b\_k)x^k
Equality: A(x)=B(x) \iff a\_k=b\_k
Multiplication: A(x)B(x) = \sum\limits\_{n=0}^\infty (\sum\limits\_{j=0}^n a\_jb\_{n-j})x^n

| | **Inverse/Composition of FPS** (not all FPS have inverses) | **Inverse/Recurrence Theorems** | |

A(x), B(x) are fps satisfying A(x)B(x)=1
ightarrow \frac{1}{(1-x)^k}=\sum\limits\_{k=0}^\infty x^k
ightarrow \[x^0]A(x)B(x)=1 - Inverse

Let A(x), B(x) be fps.
If b\_0 = 0 \Rightarrow A(B(x)) = \sum\limits\_{j=0}^\infty a\_j(B(x))^j - Composition

|

\frac{1}{(1-x)^k}=\sum\limits\_{n=0}^\infty {n+k-1 \choose k-1}x^n - Negative Binomial Theorem

Let A(x) = \sum\limits\_{j=0}^\infty a\_jx^j.
A(x) has inverse \iff \[x^0]A(x)=a\_0\ne 0

Let A(x), C(x) be fps.
If \[x^0]A(x) \ne 0 \Rightarrow there exists fps B(x) where A(x)B(x)=C(x)
Let A(x), C(x) be fps with a\_0 \ne 0. Let B(x) = \frac{C(x)}{A(x)}.
ightarrow \[x^n]B(X) = b\_n=\frac{1}{a\_0}(c\_n-\sum\limits\_{j=0}^{n-1} a\_{n-j}b\_j)

Let A(x), B(x) be fps s.t. \[x^0]A(x) \ne 0 and \[x^0]B(x)=0
ightarrow (A(B(x)))^{-1}=A^{-1}(B(x))

| | **Sum and Product Lemmas for Generating Series** | **Geometric Series** | |

Let S=A \cup B, A \cap B = \varnothing, w:S\rightarrow {0, 1,...}
\Phi\_S(x)=\Phi\_A(x)+\Phi\_B(x) - Sum lemma

Let A, B be sets with weight functions:
\alpha: A\rightarrow {0, 1, ...}
\beta: B \rightarrow {0, 1, ...}
w: A \times B \rightarrow {0, 1, ...}: w((a,b))=\alpha(a)+\beta(b)
ightarrow \Phi\_{A \times B}(x) = \Phi\_A(x) \Phi\_B(x) - Product Lemma

|

Geometric Series:
\sum\limits\_{j=0}^\infty x^j= \frac{1}{1-x} -

Composition of Geometric Series:
\[x^0]A(x)=0 \Rightarrow \sum\limits\_{j=0}^\infty (A(x))^j=\frac{1}{1-A(x)}

| | **Integer Composition** | **Ambiguous/Unambiguous Binary Strings** | |

A composition of n is a tuple of positive integers
(a\_1, a\_2, ..., a\_k) s.t. a\_1+a\_2+...+a\_k=n
k is the number of parts of the composition.

|

Let A, B be sets of binary strings.

AB is ambiguous if:
There exist a\_1, a\_2 \in A and b\_1, b\_2 \in B s.t.
a\_1b\_1=a\_2b\_2

A \cup B is unambiguous if A \cap B \ne \varnothing

Expression with several concatenation/union operations is unambiguous if 1 of the concatenations or unions is.

| | **Unambiguous/Ambiguous Binary Strings Expressions** | **Unambiguous Binary String Operations** | |

A^k is ambiguous if there are distinct k-tuples and the concatenations are equal.

A^* is unambiguous \iff
1. A^k \cap A^j = \varnothing
2. A^k is unambiguous for each k \ge 0

Unambiguous Expressions for set of all binary strings:
1. S={0, 1}^*
2. S={0}^*({1}{0}^*)^*
3. S={0}^*({1}{1}^*{0}{0}^*)^*{1}^*

|

Theorem 2.6.1:
A, B are sets of unambiguous binary strings.
(i) \Phi\_{AB}(x) = \Phi\_A(x)\Phi\_B(x)
(ii) \Phi\_{A \cup B}(x) = \Phi\_A(x)+\Phi\_B(x)
(iii) \Phi\_{A\*}(x) = \frac{1}{1-\Phi\_A(x)}

| | **Partial Fractions Theorems** | **Homogeneous Linear Recurrences** | |

f, g are polynomials where deg(f) < deg(g) and
g(x)=(1-r\_1x)^{e\_1}...(1-r\_kx)^{e\_k}
where r\_1, ..., r\_k \in \C, e\_1, .., e\_k \in \Z^+

Partial Fractions Theorem:
ightarrow \frac{f(x)}{g(x)}=\frac{c\_{1,1}}{(1-r\_1x)}+...
+\frac{c\_{1,e\_1}}{(1-r\_1x)^{e\_1}}+\frac{c\_{2,1}}{(1-r\_2x)}+...
+\frac{c\_{2,e\_2}}{(1-r\_x)^{e\_2}}+...+\frac{c\_{k,1}}{(1-r\_kx)}+...+\frac{c\_{k,e\_k}}{(1-r\_kx)^{e\_k}}

Theorem 3.1.4:
There exist polynomials P\_1, ..., P\_k s.t. deg(P\_i)\
ightarrow \[x^n]\frac{f(x)}{g(x)}=P\_1(n)r\_1^n+P\_2(n)r\_2^n+...+P\_k(n)r\_k^n

|

Theorem 3.2.1:
Let {c\_n}*{n \ge 0} satisfy the linear recurrence:
c\_n + q\_1c*{n-1}+...+q\_kc\_{n-k}=0
Define g(x)=1+q\_1x+...+q\_kx^k, C(x)=\sum\limits\_{n=0}^\infty c\_nx^n
ightarrow There exists polynomial f(x) s.t. deg(f) < k
C(x) = \frac{f(x)}{g(x)}

| | **Characteristic Polynomial** | | |

h(x)=q\_k+q\_{k-1}x+...+q\_1x^{k-1}+x^k for recurrence:
c\_n+q\_1c\_{n-1}+...+q\_kc\_{n-k}=0

Theorem:
Roots: r\_1, r\_2, ..., r\_L \in \C
Multiplicities: e\_1, e\_2, ..., e\_L \ge 1
ightarrow Then there exists polynomials P\_1, ..., P\_L s.t. deg(f\_j) = e\_j-1 and c\_n = P\_1(n)r\_1^n + ... + P\_L(n)r\_L^n

| | ## Graph Theory | Handshaking Lemma | Corollary 4.3.2 (# of odd degrees) | | ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- | ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ | | $$\sum\limits\_{v \in v(G)} deg(v)=2 | E(G) | | **Corollary 4.3.3 (Average Vertex Degree)** | **Isomorphic** | | Avg vertex degree = $$\frac{2 | E(G) | | **Isomorphic Equivalence Relation** | **Complete Graphs** ($$K\_n$$) | |

1. A graph is isomorphic to itself (reflexive)
2. If G\_1 \cong G\_2 \Rightarrow G\_2 \cong G\_1 (symmetric)
3. If G\_1 \cong G\_2 and G\_2 \cong G\_3 \Rightarrow G\_1 \cong G\_3 (transitive)

|

Every pair of vertices is an edge.
# of edges = {n \choose 2}

| | **Regular Graphs** (k-regular) | **Bipartite Graphs** | |

Graph where every vertex has degree k.
# of edges = \frac{nk}{2}

|

Graph where there exists partition of vertices (A,B) s.t. each edge
of G joins 1 vertex of B with a vertex in A.

| | **Complete Bipartite Graphs** ($$K\_{m,n}$$) | **N-cube** | |

Graph with partition (A,B) where all possible edges joining
vertex in A with vertex in B.
$$

| A | | **Theorem 4.5.2 (Walk, Path)** | **Corollary 4.6.3 (Path Transitive)** | | If there is a $$u,v$$-walk in $$G \Rightarrow$$ there is a $$u,v$$-path in $$G$$. | If there exists $$u,v$$-path and $$v,w$$-path $$ightarrow$$ there exists $$u,w$$-path. | | **Theorem 4.6.4 (Cycle, degree)** | **Girth** | | If every vertex in $$G$$ has $$deg \ge 2 \Rightarrow G$$ has a cycle. |

Length of graph's shortest cycle.
If G has no cycles ightarrow girth = \infty

- Measure of graph density
- High girth = lower average degree (usually)

| | **Spanning Cycle**/Hamiltonian Cycle | **Connectedness** | | Cycle that uses every vertex in the graph | Connected if there is a $$u,v$$-path for any pair of vertices $$u,v$$. | | **Theorem 4.8.2 (Connectedness)** | **Cuts** | |

Let u \in V(G)
If u,v-path exists for each v \in V(G) \Rightarrow G is connected.

|

Let x \subseteq V(G).
Cut induced by x in G is the set of all edges in G with exactly 1 end in x.

| | **Theorem 4.8.5 (Disconnectedness)** | **Eulerian Circuit/Tour** | |

G is disconnected \iff
There exists a nonempty proper subset x of V(G)
s.t. the cut induced by x is \empty.

|

Closed walk that uses every edge of G exactly once.
- Connected unless it has isolated vertices

| | **Theorem 4.9.2 (Eulerian Circuit Vertices)** | **Bridge** | |

G is connected.
G has an Eulerian circuit \iff every vertex in G has even degree.

| An edge $$e$$ (or cut-edge) in $$G$$ if $$G-e$$ has more components than $$G$$. | | **Lemma 4.10.2 (Bridge Component)** | **Theorem 4.10.3 (Bridge, Cycle)** | |

If e=uv is a bridge in G and H is the component containing e
ightarrow H-e has exactly 2 components
(hence G-e has 1 more component than $G$)
Moreover, u and v are in different components of H-e.
(hence in G-e)

| An edge $$e$$ is a bridge of $$G$$ $$\iff$$ $$e$$ is not in any cyce of $$G$$. | | **Tree** | **Forest** | |

Connected graph with no cycles
# of edges = n-1 by Theorem 5.1.5
- Bipartite by Lemma 5.1.4

|

Graph with no cycles.
# of edges = n-k , with n vertices and k components

| | **Lemma 5.1.4 (Tree, Bridge)** | **Leaf** | | Every edge in a tree/forest is a bridge. | Tree with vertex degree 1. | | **Theorem 5.1.8 (Tree Leaves)** | **Lemma 5.1.3 (Unique Path Tree)** | | Every tree with $$\ge 2$$ vertices has $$\ge 2$$ leaves. | There is a unique path between any 2 vertices in a tree. | | **Theorem 5.2.1 (Connectedness, Spanning tree)** | **Corollary 5.2.2 (Connected, tree)** | | $$G$$ is connected $$\iff G$$ has a spanning tree. | If $$G$$ is connected with $$n$$ vertices and $$n-1$$ edges $$ightarrow G$$ is a tree. | | **Corollary (Tree-Graph equivalence)** | **Corollary 5.2.3 (Spanning Tree, Cycle)** | |

If any of 2 the following 3 conditions hold ightarrow G is a tree:
1. G is connected
2. G has no cycles.
3. G has n-1 edges.

|

If T is a spanning tree of G and e is an edge in G that is not in T
ightarrow T+e has exactly 1 cycle.
Moreover, if e' is an edge in C
ightarrow T+e-e' is a spanning tree of G.

| | **Corollary 5.2.4 (Spanning Tree, Component)** | **Bipartite Characterization Theorem** | |

If T is a spanning tree of G and e is an edge in T
ightarrow T-e has 2 components (e is a bridge in T).
If e' is an edge in the cut induced by the vertices of 1 component
ightarrow T-e+e' is a spanning tree of G.

| $$G$$ is bipartite $$\iff G$$ has no odd cycles. | | **Minimum Spanning Tree (MST) Problem** | **Prim's Algorithm Theorem** | |

Given connected graph G and weight function on edges
w: E(G) \rightarrow , find minimum spanning tree in G
whose total edge weight in minimized.

| Prim's algorithm produces a MST. | | **Complement** | **Planar** | | If 2 vertices are adjacent in $$G \iff$$The same 2 vertices are not adjacent in $$\bar{G}$$. | A graph is planar $$\iff$$ Each component is planar | | **Face** | **Boundary** | |

A face of a planar embedding is a connected region on the plane.
2 faces are adjacent $\iff$ The faces share \ge 1 edge in their boundaries.

| Subgraph of all vertices and edges that touch a face. | | **Boundary Walk** | **Handshaking Lemma for Faces** | |

Closed walk once around the perimeter of the face boundary.
Degree of face = length of boundary walk

|

Let G be a planar graph with planar embedding where F is the set of all faces.
$$\sum\limits\_{f \in F} deg(f)=2

| | **Lemma L7-1** | **Jordan Curve Theorem** | |

In a planar embedding, an edge e is a bridge
\iff The 2 sides of e are in the same face

|

Every planar embedding of a cycle separates the plane into
2 parts: 1 on the inside, 1 on the outside

| | **Euler's Formula** | **Platonic** | |

Let G be a connected planar graph.
Let n = # of vertices in G.
Let m = # of edges in G.
Let s = # of faces in a planar embedding of G.
ightarrow n-m+s=2
Note: If G has C components ightarrow n-m+s=1+C
Result: All planar embeddings of a graph have the same number of faces.

|

A connected planar graph is platonic if it has a planar embedding
where every vertex has same degree (\ge 3) AND
every face has same degree (\ge 3)

| | **Lemma 7.5.2** | **Lemma 7.5.1** | |

Let G be a planar graph with n vertices and m edges.
If there is a planar embedding of G where every face has degree \ge 3
ightarrow m \le \frac{d(n-2)}{d-2}

|

If G contains a cycle
ightarrow In any planar embedding of G, every face boundary contains a cycle.

| | **Theorem 7.5.3** | **Corollary 7.5.4** | |

Let G be a planar graph with n \ge 3 vertices
ightarrow m \le 3n-6

| $$K\_5$$ is not planar. | | **Theorem 7.5.6** | **Corollary 7.5.7** | |

Let G be a bipartite planar graph with \ge 3 vertices and m edges.
ightarrow m \le 2n-4

| $$K\_{3,3}$$ is not planar. | | **Edge Subdivision** | **Kuratowski's Theorem** | |

Edge subdivision of G is obtained by replacing each edge of G
with a new path of length \ge 1

|

A graph is planar
\iff Graph does not have an edge subdivision of K\_5 or K\_{3,3} as a subgraph.

| | **K-colouring** | **Theorem 7.7.2** | |

If C is a set of size k ("colours")
ightarrow f:V(G) \rightarrow C s.t. f(u) \ne f(v) \space \forall uv \in E(G)
Note: A k-colouring does not need to use all k colours.

| $$G$$ is 2-colourable $$\iff$$ $$G$$ is bipartite | | **Theorem 7.7.3** | **6-Colour Theorem** | | $$K\_n$$ (complete graph) is n-colourable, and not k-colourable for any $$k\Key: Colouring faces is equivalent to colouring vertices of dual graph.
The dual graph is planar.
1. If G is connected ightarrow (G^*)^*=G
2. A vertex in G corresponds to a face in G^* of the same degree.
3. A face in G corresponds to a vertex in G^* of the same degree.
4. The dual of a platonic graph is platonic.
5. If we draw a closed curve on the plane ightarrow the faces are 2-colourable.

|

If M is any matching of G and C is any cover in G
$$\Rightarrow

| | **Lemma 8.2.2** | **Konig's Theorem** | | If $$M$$ is a matching of $$G$$ and $$C$$ is a cover of $$G$$ where $$ | M | | **Augmenting Path Results L8-2** | **Lemma 8.1.1** | |

Let M be a matching.
Let P be an augmenting path.
Let M' be a new matching from P.
ightarrow M'=\[M\cup (E(P)\setminus M)]\space \setminus (E(P)\cap M)
Notes:
- P is always odd length (L8-2 for proof)
- P always starts and ends in different parts of the bipartition.

| If a matching $$M$$ has an augmenting path $$ightarrow$$ $$M$$ is not a maximum. | | **Bipartite Matching Algorithm** | **Corollary L8-4** | | Minimum cover = $$Y \cup (A \setminus X)$$ |

A bipartite graph G with m edges and maximum degree d
has a matching of size \ge \frac{m}{d}

| | **Neighbour Set** ($$N\_G(D)$$ or $$N(D)$$) | **Hall's Theorem** | |

Let D \subseteq V(G).
Neighbour set of D is set of all vertices adjacent to at least 1 vertex in D.

|

A bipartite graph G with bipartition (A,B) has a matching that saturates all vertices in A
$$\iff \space \forall \space D \subseteq A,

| | **Corollary 8.6.2** | **Corollary L8-6** | |

If G is a k-regular bipartite graph with k\ge 1
ightarrow G has a perfect matching.

| The edges of a $$k$$-regular bipartite graph can be partitioned into $$k$$ perfect matchings. | !\[]\(/Users/lauradang/Desktop/MATH 239/117236022\_304925684278221\_7724805982347918422\_n.jpg)