Graph Theory Fundamentals

• Sets: a graph is a pair of sets; $\binom{n}{2}$ counts 2-element subsets.

Definitions and conventions

• Unless stated otherwise, "graph" means a simple undirected graph: no loops (edge from a vertex to itself) and no multiple edges between the same pair. Then an edge is a 2-element subset $\{u, v\}$ and $m \le \binom{n}{2}$.
• A multigraph allows multiple edges; a pseudograph also allows loops. A directed graph (digraph) has ordered pairs $(u, v)$ as arcs.
• Degree $\deg(v)$ is the number of edge ends at $v$. A loop counts twice toward the degree of its vertex, so the handshake lemma below holds for pseudographs too.
• In a digraph, $\deg^{-}(v)$ (in-degree) and $\deg^{+}(v)$ (out-degree) count arcs entering and leaving $v$.

The handshake lemma

• The number of odd-degree vertices is even.
• A $k$-regular graph on $n$ vertices has $m = kn/2$ edges, so $kn$ must be even (no 3-regular graph on 7 vertices exists).
• For a digraph, $\sum \deg^{-}(v) = \sum \deg^{+}(v) = m$.
• Average degree is $2m/n$, so $\delta \le 2m/n \le \Delta$.

Degree sequences

Special graphs

Bipartite graphs

Subgraphs, complements, isomorphism

• $H$ is a subgraph of $G$ if $V(H) \subseteq V(G)$ and $E(H) \subseteq E(G)$. It is induced if it contains every edge of $G$ between its vertices; spanning if $V(H) = V(G)$.
• The complement $\overline{G}$ has the same vertices and exactly the edges missing from $G$: $m(G) + m(\overline{G}) = \binom{n}{2}$. A self-complementary graph is isomorphic to its complement, which forces $\binom{n}{2}$ even, so $n \equiv 0$ or $1 \pmod 4$.
• $G$ and $H$ are isomorphic if a bijection $f : V(G) \to V(H)$ preserves adjacency in both directions. Invariants (equal in isomorphic graphs): $n$, $m$, degree sequence, number of cycles of each length, connectedness, bipartiteness. Matching invariants do not prove isomorphism; one differing invariant disproves it.
• The number of labelled simple graphs on a fixed set of $n$ vertices is $2^{\binom{n}{2}}$; the number with exactly $m$ edges is $\binom{\binom{n}{2}}{m}$.

Walks, paths, cycles

• A walk is a sequence of vertices with consecutive ones adjacent; its length is the number of edges.
• A trail repeats no edge; a path repeats no vertex. A cycle is a closed path of length at least 3.
• The number of walks of length $k$ from $u$ to $v$ is the $(u, v)$ entry of $A^k$, where $A$ is the adjacency matrix.
• If every vertex has degree at least 2, the graph contains a cycle. A connected graph with $n$ vertices and no cycle is a tree and has exactly $n - 1$ edges; a forest with $c$ components has $n - c$ edges. Trees are developed in Trees and Binary Trees.

Euler and Hamiltonian graphs

• An Euler circuit traverses every edge exactly once and returns to its start; an Euler path (trail) traverses every edge exactly once.
• Euler's theorem. A connected (multi)graph, ignoring isolated vertices, has an Euler circuit if and only if every vertex has even degree, and an Euler path but no Euler circuit if and only if exactly two vertices have odd degree (the path starts at one and ends at the other).
• A Hamiltonian cycle visits every vertex exactly once and returns; a Hamiltonian path visits every vertex exactly once. No simple necessary-and-sufficient condition is known, and deciding it is NP-complete.
• Sufficient conditions (simple graph, $n \ge 3$): Dirac: $\delta(G) \ge n/2$. Ore: $\deg(u) + \deg(v) \ge n$ for every pair of non-adjacent $u, v$. These are not necessary: $C_n$ is Hamiltonian with all degrees 2.
• Necessary condition: for every nonempty $S\subseteq V$ in a Hamiltonian graph, $c(G-S)\le|S|$. A bipartite graph with unequal part sizes has no Hamiltonian cycle.

Planar graphs

• Euler's formula: for a connected planar graph, $n - m + f = 2$; with $c$ components, $n - m + f = 1 + c$.
• For a simple connected planar graph with $n \ge 3$: $m \le 3n - 6$. If it also has no triangle (for example, if it is bipartite): $m \le 2n - 4$.
• Consequences: $K_5$ ($m = 10 > 9$) and $K_{3,3}$ ($m = 9 > 8$) are non-planar. Every simple planar graph has a vertex of degree at most 5.
• Kuratowski's theorem: a graph is planar if and only if it has no subgraph that is a subdivision of $K_5$ or $K_{3,3}$.
• The bounds $m \le 3n - 6$ and $m \le 2n - 4$ are necessary, not sufficient: satisfying them does not prove planarity.

Example 1: handshake

Example 2: planar faces

Example 3: Euler paths

Example 4: counting graphs

• In any simple graph with $n \ge 2$, two vertices have the same degree (pigeonhole: degrees 0 and $n - 1$ cannot both occur).
• $G$ or $\overline{G}$ is connected (for every $G$).
• $Q_k$ is bipartite (split by parity of the number of 1 bits) and Hamiltonian for $k \ge 2$ (Gray code).
• A tree with $n \ge 2$ vertices has at least two leaves.
• $K_n$ has $n!/(2n) = (n-1)!/2$ distinct Hamiltonian cycles for $n \ge 3$.

• Counting edges and vertices. Handshake lemma, special-graph formulas, Euler's formula for planar graphs.
• Degree-sequence questions. Check parity, maximum degree, then Havel-Hakimi.
• Euler and Hamilton. Euler: parity of degrees, an exact characterisation. Hamilton: only sufficient conditions (Dirac, Ore) and necessary obstacles.
• Planarity. Use $m \le 3n - 6$ (or $2n - 4$ without triangles) to rule out planarity.
• Trap: whether loops count once or twice. These notes count a loop twice.
• Trap: Dirac's and Ore's conditions are sufficient, not necessary.

• Sets: prerequisite.
• Graph Connectivity: dependent. Components, cut vertices and bridges.
• Matching in Graphs: dependent. Matchings, especially in bipartite graphs.
• Graph Colouring: dependent. Chromatic number, bipartite and planar graphs.
• Graph Representations: dependent. Adjacency matrix and adjacency lists.
• Trees and Binary Trees: related. Trees as acyclic connected graphs.