Summary of graph theory

Basic concepts.
- Order $|V|$, size $|E|$, degree, handshake lemma $\sum\deg=2|E|$.
- Walk, path, cycle, connectivity, connected components.
- Complete graph $K_n$, complement, bipartite.

Trees.
- Tree = connected acyclic graph.
- $n-1$ edges; equivalent characterizations.
- Cayley's formula: $n^{n-2}$ labeled trees.
- Prüfer sequences.

Algorithms.
- BFS, DFS, Dijkstra, Kruskal, Prim.

Planarity.
- Euler's formula $v-e+f=2$.
- $e\le3v-6$ for planar; $e\le2v-4$ for bipartite planar.
- $K_5$ and $K_{3,3}$ are non-planar.
- Kuratowski's theorem.

Coloring.
- Chromatic number $\chi(G)$.
- Four-color theorem: $\chi\le4$ for planar.
- Vizing's theorem on edge coloring.

Matching and flow.
- Hall's marriage theorem, Kőnig's theorem.

Extremal.
- Turán's theorem, Ramsey numbers, Szemerédi's regularity lemma.

Conclusion. Graph theory is a rich area connecting combinatorics, algorithms, topology, and algebra.