**Maintainer:**admin

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

*1*Matching¶

*1.1*Stable 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.2*Gale-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.3*Hall'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.4*d-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.5*Definition 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.6*Latin 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.

*2*Graph Coloring¶

*2.1*Edge 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.2*Vizing's theorem¶

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

*3*Planar Graphs¶

*3.1*Euler'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.2*6-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.3*5-color Theorem¶

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

*3.4*4-color Theorem¶

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

*3.5*Art Gallery Theorem¶

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

*3.6*Definition 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.7*Kuratowski's theorem¶

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

*3.8*Fary'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

*4*Other Graph Theorems¶

*4.1*Menge(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)