Home MATH 340 Winter 2014 Pre-Midterm Theorem Summary

Winter 2014 Pre-Midterm Theorem Summary CC-BY-NC

Maintainer: admin

Some of the definition and theorems are taken verbatim from Winter 2014 Lecture Notes maintained by @dellsystem

1Matching

1.1Stable Marriage

Marriage between set of men $A$ and women $B$ is stable if and only if no man-woman pair prefer each other over their currently married ones.

Proof of existence of stable marriage is constructive by Gale-Shapley.

1.2Gale-Shapley Method

Each man propose to his most preferred woman who hasn't yet refused his proposal. Each woman will accept a proposal, if she prefers the candidate over her current spouse.

1.3Hall's theorem

A bipartite graph with equal-sized partitions $X$, $Y$ has a perfect matching $\iff$ for all $A \subseteq X$, $|\Gamma(A)| \geq |A|$

1.4d-regularity in bipartite graph

A $d$-regular, bipartite graph can be decomposed into $d$ edge-disjoint perfect matchings. Proof is by induction on $d$.

1.5Definition of Latin rectangle

A Latin rectangle is a r×n grid (with $n>r$) containing some subset of the numbers $1,\dots,n$ such that each number only appears at most once in each row and column.

1.6Latin rectangle extendability

Every Latin rectangle can be extended to get a n×n Latin square. The idea of the proof summarizes to the following: Create a bipartite graph where one partition contains the columns, the other contains the numbers. Create an edge between column and number if the number does not appear in the column. This gives a $(n-r)$-regular bipartite graph, where each matching is a valid row to be appended.

2Graph Coloring

2.1Edge chromatic number

Edge chromatic number $\chi^E(G)$ is the min number of colors required to color edges of $G$ such that no adjacent edges share the same color.

In bipartite graph $\Delta(G) = \chi^E(G)$. Proof is by completing the graph with dummy edges to form a d-regular bipartite graph where $d = \Delta(G)$. Each edge-disjoin perfect matching can be 1-colored.

2.2Vizing's theorem

$\Delta(G) \leq \chi^E(G) \leq \Delta(G)+1$. Proof is not required for this course.

3Planar Graphs

3.1Euler's Theorem

A connected planar graph satisfies $m+2=n+f$. where $m$ is number of edges, $n$ number of vertices, $f$ number of faces

3.26-color Theorem

A planar graph can be 6-colored. The proof follows directly from a corollary of Euler's theorem i.e. there's a vertex whose degree is at most 5.

3.35-color Theorem

A planar graph can be 5-colored. The proof is a little longer, subjected to case by case analysis.

3.44-color Theorem

A planar graph can be 4-colored. This is not human-provable

3.5Art Gallery Theorem

At worst case ${n}\over{3}$ guards are necessary to guard a room, where $n$ is the number of vertices

3.6Definition of Graph Minor

$H$ is called a minor of the graph $G$ if $H$ can be formed from $G$ by deleting edges and vertices and by contracting edges.

3.7Kuratowski's theorem

A graph $G$ is planar if and only if there is no $K_5$ nor $K_{3,3}$ minor in that

3.8Fary's Theorem

Any simple planar graph can be drawn without crossing using only straight lines.

Proof: http://en.wikipedia.org/wiki/F%C3%A1ry's_theorem

4Other Graph Theorems

4.1Menge(1927)'s Theorem

Given a graph $G=(V,E)$ and $s,t \in V$. The max number of disjoint s-t paths $=$ min number of vertices that separates $s$ from $t$.

Proof: Diestel's book (Section 3.3)