Graph Theory – Complete Formula Sheet

1. Basic Definitions

Graph Notation

$G = (V, E)$ where $|V|=n$, $|E|=m$

$V$: Set of vertices

$E$: Set of edges/arcs

Degree & Incidence

$\deg(v)$ = # edges incident to $v$

$\deg^{in}(v)$ = in-degree (directed)

$\deg^{out}(v)$ = out-degree (directed)

$u \sim v$ : adjacent vertices

Neighborhoods

$N(v) = \{u : (u,v) \in E\}$

$N[v] = N(v) \cup \{v\}$

Open vs closed neighborhood

Edge Classification

Loop: Edge from vertex to itself

Multi-edge: Multiple edges between pair

Simple graph: No loops, no multi-edges

2. Types of Graphs

Standard Classes

Simple: No loops or multi-edges

Multigraph: Multiple edges allowed

Directed: Edges have direction

Weighted: $w: E \to \mathbb{R}$

Complete Graphs

$K_n$: All pairs connected

$|E(K_n)| = \frac{n(n-1)}{2}$

$K_n$ is $(n-1)$-regular

Bipartite Graphs

$G = (A \cup B, E)$ with $A \cap B = \emptyset$

$K_{m,n}$: Complete bipartite

$|E(K_{m,n})| = mn$

Path & Cycle

$P_n$: Path with $n$ vertices

$C_n$: Cycle with $n$ vertices

Star $S_n$: Central + $n$ leaves

3. Graph Representations

Adjacency Matrix

$A \in \{0,1\}^{n \times n}$

$A[i][j] = 1$ if $(i,j) \in E$

Symmetric for undirected

Space: $O(|V|^2)$

Adjacency List

List of neighbors per vertex

Space: $O(|V| + |E|)$

Efficient for sparse graphs

Edge List

Explicit list of all edges

Space: $O(|E|)$

Incidence Matrix

$|V| \times |E|$ matrix

$M[i][j] = 1$ if vertex $i$ touches edge $j$

4. Handshaking Lemma

Fundamental Theorem

$\sum_{v \in V} \deg(v) = 2|E|$

Sum of all degrees = 2 × edge count

Degree Count

Average degree: $\bar{d} = \frac{2|E|}{|V|}$

Number of odd-degree vertices is EVEN

Degree Sequence

Sorted: $d_1 \geq d_2 \geq ... \geq d_n$

Graphical iff even sum exists

Regular Graphs

$k$-regular: All $\deg(v) = k$

$|E| = \frac{kn}{2}$ (if even)

5. Paths & Walks

Walk Terminology

Walk: Sequence of vertices/edges

Trail: Walk with distinct edges

Path: Walk with distinct vertices

Cycle: Closed path (≥3 vertices)

Distance Metrics

$d(u,v)$ = length of shortest path

$\text{diam}(G) = \max_{u,v} d(u,v)$

$\text{rad}(G) = \min_v \max_u d(u,v)$

Path Properties

Triangle inequality: $d(u,w) \leq d(u,v)+d(v,w)$

Symmetric: $d(u,v) = d(v,u)$

Cycle

Girth: Length of shortest cycle

Circumference: Longest cycle length

6. Connectivity

Connected Components

$\omega(G)$ = # connected components

Maximal connected subgraphs

Connectivity Numbers

$\kappa(G)$ = vertex connectivity

Min vertices to remove for disconnect

$\lambda(G)$ = edge connectivity

Min edges to remove for disconnect

Bridges & Cut Vertices

Bridge: Removal increases $\omega(G)$

Cut vertex: Removal increases $\omega(G)$

Blocks

Maximal 2-connected subgraph

Contains no cut vertices

7. Trees

Tree Properties

$|E| = |V| - 1$

Connected and acyclic

Unique path between any two vertices

Tree Characterization

$n$ vertices, $n-1$ edges, connected

$n$ vertices, $n-1$ edges, acyclic

Any two properties imply the third

Leaves

Pendant vertices: $\deg(v) = 1$

Tree with $n \geq 2$ has $\geq 2$ leaves

Spanning Trees

$\tau(K_n) = n^{n-2}$ (Cayley)

Connected graph has spanning tree

8. Bipartite Graphs

Definition & Testing

$V = A \cup B$, edges between parts only

Bipartite iff no odd cycles

2-colorable graph

Complete Bipartite

$K_{m,n}$: Every $a \in A$ to every $b \in B$

$|E(K_{m,n})| = mn$

$|V(K_{m,n})| = m + n$

Matching in Bipartite

Hall's Marriage Theorem

Perfect matching exists iff $|N(S)| \geq |S|$ for all $S \subseteq A$

König's Theorem

Max matching = Min vertex cover (bipartite only)

9. Eulerian Graphs

Definitions

Eulerian circuit: Each edge exactly once, returns to start

Eulerian path: Each edge exactly once, different start/end

Euler's Theorem

Circuit exists iff ALL vertices have EVEN degree

Path exists iff exactly 2 vertices have ODD degree

Conditions

Graph must be connected

No isolated vertices allowed

Algorithm

Hierholzer's algorithm: $O(|E|)$ time

10. Hamiltonian Graphs

Definitions

Hamiltonian cycle: All vertices once, return to start

Hamiltonian path: All vertices once, different start/end

Sufficient Conditions

Dirac: $\deg(v) \geq \frac{n}{2}$ for all $v$

Ore: $\deg(u)+\deg(v) \geq n$ for non-adjacent $u,v$

Hardness

Finding Hamiltonian cycle is NP-Complete

No known polynomial algorithm

Petersen's Theorem

Every 3-regular bridgeless graph has perfect matching

11. Planar Graphs

Definition

Can be drawn without edge crossings

Euler's Formula

$|V| - |E| + |F| = 2$

For connected planar graphs

Edge Bounds

$|E| \leq 3|V| - 6$

Bipartite: $|E| \leq 2|V| - 4$

Non-Planarity Tests

Kuratowski: Planar iff no $K_5$ or $K_{3,3}$ subdivision

$K_5, K_{3,3}$ are non-planar

4-Color Theorem

$\chi(G) \leq 4$ for planar graphs

12. Graph Coloring

Chromatic Number

$\chi(G)$ = minimum colors needed

Adjacent vertices must have different colors

Bounds

$\chi(G) \leq \Delta(G) + 1$

$\chi(G) \geq \frac{|V|}{\alpha(G)}$

$\chi(G) \geq \omega(G)$ (clique number)

Special Cases

Bipartite: $\chi(G) = 2$ iff no odd cycles

$\chi(K_n) = n$

$\chi(C_n) = 2$ if $n$ even, 3 if $n$ odd

Algorithms

Greedy: $O(|V|^2)$ worst case

Exact coloring: NP-Complete

13. Matching

Definitions

Matching: No two edges share endpoint

Perfect: All $|V|$ vertices matched

Maximum: Most edges in matching

Augmenting Paths

Starts and ends in unmatched vertices

Alternating matched/unmatched edges

Hall's Marriage Theorem

$|N(S)| \geq |S|$ for all $S \subseteq A$

Perfect matching exists in bipartite

König & Tutte

König: Max matching = Min cover (bipartite)

Tutte-Berge: General graphs

14. Network Flow

Flow Constraints

$0 \leq f(e) \leq c(e)$ (capacity)

Flow conservation: $\sum_{in} f = \sum_{out} f$

Max-Flow Min-Cut

Maximum flow = Minimum cut capacity

Cut: Edge set separating source & sink

Ford-Fulkerson Algorithm

$O(|E| \cdot \text{max flow})$

Find augmenting paths in residual graph

Edmonds-Karp

$O(|V| \cdot |E|^2)$

BFS for shortest augmenting path

15. Shortest Paths

Dijkstra's Algorithm

$O((|V|+|E|)\log|V|)$ with heap

Non-negative weights only

Single source to all vertices

Bellman-Ford Algorithm

$O(|V| \cdot |E|)$

Handles negative weights

Detects negative cycles

Floyd-Warshall Algorithm

$O(|V|^3)$

All-pairs shortest paths

Dynamic programming approach

Transitive Closure

$TC(G)[i,j] = 1$ if path exists from $i$ to $j$

16. Min Spanning Trees

MST Definition

Spanning tree with minimum total weight

Weight = sum of all edge weights

Prim's Algorithm

$O((|V|+|E|)\log|V|)$ with heap

Grow tree from single vertex

Kruskal's Algorithm

$O(|E| \log |E|)$

Sort edges, add non-cycle edges

Uses Union-Find data structure

Unique MST

If all weights distinct, MST is unique

17. Strongly Connected Components

Definition

SCC: Maximal subgraph where every vertex reaches every other

For directed graphs only

Kosaraju's Algorithm

$O(|V| + |E|)$

Two DFS passes

Uses finish time ordering

Tarjan's Algorithm

$O(|V| + |E|)$

Single DFS with stack

Condensation DAG

Contract SCCs to single node

Result is always a DAG

18. Topological Sorting

Definition

Linear ordering of vertices such that $(u,v) \in E \Rightarrow u$ before $v$

Only for DAGs (directed acyclic graphs)

DFS Approach

$O(|V| + |E|)$

Post-order traversal in reverse

Kahn's Algorithm

$O(|V| + |E|)$

Process vertices with in-degree 0

Applications

Task scheduling, dependency resolution

Detecting cycles (if sort impossible)

19. Special Graphs

Complete Graph $K_n$

$|E| = \frac{n(n-1)}{2}$

$\chi(K_n) = n$, $\kappa(K_n) = n-1$

Petersen Graph

10 vertices, 15 edges, 3-regular

Non-planar, girth 5

Hypercube $Q_n$

$2^n$ vertices, $n \cdot 2^{n-1}$ edges

$n$-regular, bipartite, diameter $n$

Wheel $W_n$

Central vertex + cycle $C_n$

$n+1$ vertices, $2n$ edges

20. Applications

Social Networks

Vertices: Users/accounts

Edges: Friendships/connections

Clustering coefficient, centrality measures

Scheduling & Dependencies

Topological sort for task ordering

Graph coloring for resource allocation

Transportation Networks

Shortest paths for routing

MST for network design

Other Applications

Matching in bipartite graphs (assignments)

Flow networks (traffic, electricity)

Web page ranking, recommendation systems

Algorithm Complexity Summary

Core Traversals

DFS/BFS: $O(|V| + |E|)$

Single-Source Shortest

Dijkstra: $O((|V|+|E|)\log|V|)$

Bellman-Ford: $O(|V| \cdot |E|)$

All-Pairs Shortest

Floyd-Warshall: $O(|V|^3)$

Spanning Trees

Prim: $O((|V|+|E|)\log|V|)$

Kruskal: $O(|E| \log|E|)$

NP-Complete Problems

Hamiltonian path/cycle

Graph coloring

Max clique, traveling salesman

Key Theorems

Handshaking Lemma

$\sum_{v} \deg(v) = 2|E|$

Euler's Formula

$|V| - |E| + |F| = 2$ (planar)

Ore's Theorem

If $\deg(u)+\deg(v) \geq n$ for all non-adjacent $u,v$, then Hamiltonian cycle exists

Max-Flow Min-Cut

Maximum flow equals minimum cut capacity

König's Theorem

Bipartite: max matching = min vertex cover

Hall's Marriage

Perfect matching in bipartite iff condition holds

Graph Invariants & Measures

Clique & Independent Set

$\omega(G)$ = max clique size

$\alpha(G)$ = max independent set

$\omega(G) \cdot \alpha(G) \geq |V|$

Vertex/Edge Cover

$\tau(G)$ = min vertex cover

$\nu(G)$ = max matching

Eccentricity

$e(v) = \max_u d(u,v)$

Center: Vertices with min eccentricity

Centrality Measures

Degree centrality

Betweenness centrality

Closeness centrality

Random Graphs

Erdős–Rényi Model

$G(n,p)$: Each edge included with probability $p$

Expected edges: $\binom{n}{2} \cdot p$

Threshold Phenomena

Phase transition at $p = \frac{1}{n}$

Connectivity threshold, giant component

Random Walk

Markov process on graph vertices

Hit time, commute time metrics

Spectral Properties

Eigenvalues of adjacency matrix $A$

Spectral gap, expansion properties

Quick Reference Formulas

Graph Properties

$\delta(G)$ = min degree

$\Delta(G)$ = max degree

Size Bounds

Simple: $|E| \leq \binom{|V|}{2}$

$k$-regular: $|E| = \frac{k|V|}{2}$

Distance Relations

$2 \cdot \text{rad} - 1 \leq \text{diam} \leq 2 \cdot \text{rad}$

Counting

Paths $P_n$: 1 edge, $n-1$ vertices

Complete: $\binom{n}{2}$ edges

GRAPH THEORY Complete Formula Sheet