Discrete-structures 06

Corollaries of Hall’s theorem

Vertex cover definition

Let denote the size of the maximum matching in and denote the size of a minimum vertex cover in

Konig-Egervary theorem theorem

---

Planar graphs

Planar embedding definition

Euler’s formula theorem

Upper bound on the number of edges in planar graphs theorem

This upped bound is in fact tight for planar graphs with each face being a triangle. Such graphs are called triangulated.

Corollary of the edge number upper bound

More corollaries

---

---

---

Graph minor definition

Planarity of graph minors lemma

Wagner-Kuratowski theorem theorem

---

---

Chromatic numbers

-coloring and Chromatic number definition

---

---

---

---

Interval graph definition