Why graphs?

Graphs capture relations: who talks to whom, which states are reachable, which components touch. A graph $G=(V,E)$ has vertices $V$ and edges $E\subseteq V\times V$ (undirected if $(u,v)\in E \Rightarrow (v,u)\in E$). The adjacency matrix $A\in\{0,1\}^{|V|\times|V|}$ records edges; $A_{uv}=1$ if $u\to v$.

Matrix powers count walks: $(A^k)_{uv}$ is the number of length-$k$ walks from $u$ to $v$. Add edge weights to model costs, capacities, or affinities.

Local structure

• Degree: $\deg(u)=\sum_v A_{uv}$; the diagonal of $D=\operatorname{diag}(\deg(u))$ collects degrees.
• Paths & cycles: reachability (BFS) and structure (cycles vs. acyclic). Trees are connected, acyclic graphs.
• Special families: DAGs (topo order), bipartite graphs (2-colorable, no odd cycles), planar graphs (drawn without crossings).

Traversal and shortest paths

Breadth‑first search (BFS) explores in layers and yields shortest paths in unweighted graphs. For nonnegative weights, Dijkstra finds shortest paths; allowing negative edges, Bellman–Ford detects negative cycles and computes shortest distances when they don’t exist.

Spanning trees and cuts

A spanning tree touches all vertices with $|V|-1$ edges. With positive weights, minimum spanning trees (MSTs) can be found by Kruskal (sort edges; greedy add if no cycle) or Prim (grow a frontier). Cuts partition $V=S\cup \bar S$; their capacity is the sum of crossing edge weights. The max‑flow min‑cut theorem ties maximum flow from $s$ to $t$ to the minimum $s\!:\!t$ cut capacity.

Spectra: smoothness and clusters

The (combinatorial) Laplacian is $L=D-A$. For a vector $x\in\mathbb{R}^{|V|}$ defined on nodes, the Dirichlet energy

$$\mathcal{E}(x)=x^\top L x = \frac{1}{2}\sum_{(u,v)\in E} w_{uv}\,(x_u-x_v)^2$$

is small when adjacent nodes have similar values (often read as “smooth” over the graph). The smallest eigenvalue is $0$ with eigenvector $\mathbf{1}$. The second eigenvector (the Fiedler vector) approximately separates the graph into two balanced parts with a small cut; this underpins spectral clustering.

Random walks and diffusion

A random walk moves $u\to v$ with probability proportional to weight $w_{uv}$. Normalized operators (e.g., $L_{\text{rw}}=I-D^{-1}A$) govern diffusion and hitting times. Many ranking and centrality measures are walk‑based: degree centrality, PageRank, betweenness and closeness centrality.

Graphs in algorithms and learning

• Programs and automata: control‑flow graphs; DFA/NFA state diagrams are directed graphs; reachability and language acceptance are path questions.
• Optimization: flows, matchings, cuts, and network design (MST, Steiner trees).
• Message passing: graph neural networks update node features by aggregating neighbors (learned, weighted versions of $A$ or $D^{-1}A$).

Planarity and Euler’s formula

Planar graphs satisfy $V - E + F = 2$ in any planar embedding (Euler characteristic). Non‑planarity is characterized by subdivisions of $K_5$ or $K_{3,3}$ (Kuratowski). These constraints inform routing, VLSI, and visualization.

A compact toolbox

• Adjacency $A$ for combinatorics; Laplacian $L$ for smoothness, diffusion, and cuts.
• BFS/DFS for reachability, topological order, and components.
• Shortest paths (Dijkstra/Bellman‑Ford), MST (Kruskal/Prim), max‑flow (Edmonds–Karp/Dinic).
• Spectral intuition for clustering and semi‑supervised learning.