Social networks are naturally modeled as graphs where vertices represent individuals and edges represent relationships (friendship, following, collaboration). Properties like clustering coefficient, average path length, and degree distribution reveal network structure.

Small-world property: Many real networks exhibit short average path lengths (small diameter) despite large size. The famous "six degrees of separation" suggests that any two people are connected by a path of length around 6.

Scale-free networks: Degree distributions following power laws $P(k) \propto k^{-\gamma}$, with many low-degree vertices and few high-degree "hubs." Examples include the internet topology and citation networks.

The Four Color Theorem (proved 1976) states that any planar graph can be colored with at most 4 colors. Applications include:

• Map coloring: Countries as vertices, borders as edges
• Register allocation: Variables as vertices, conflicts as edges (variables that can't share registers)
• Scheduling: Tasks as vertices, conflicts as edges (tasks that can't run simultaneously)
• Sudoku: Each cell is a vertex, edges connect cells in the same row, column, or 3×3 box

Finding the chromatic number is NP-hard in general, but certain graph classes (bipartite, planar, perfect graphs) have polynomial-time algorithms.

An Eulerian path visits every edge exactly once. An Eulerian circuit is an Eulerian path that starts and ends at the same vertex.

Euler's Theorem: A connected graph has an Eulerian circuit if and only if every vertex has even degree. It has an Eulerian path (but not circuit) if and only if exactly two vertices have odd degree.

A Hamiltonian path visits every vertex exactly once. A Hamiltonian cycle is a Hamiltonian path that returns to the start vertex.

Unlike Eulerian paths (polynomial-time decidable), determining whether a Hamiltonian cycle exists is NP-complete. The Traveling Salesman Problem seeks the shortest Hamiltonian cycle in a weighted graph.

A matching in a graph is a set of edges with no common vertices. A perfect matching covers all vertices. Matching problems arise in:

• Job assignment: Workers and jobs as bipartite graph vertices
• Organ donation chains: Donors and recipients
• Stable marriage problem: Finding stable matchings in bipartite graphs with preferences

Hall's Marriage Theorem: A bipartite graph $G = (X \cup Y, E)$ has a matching covering $X$ if and only if for every subset $S \subseteq X$, the neighborhood $|N(S)| \geq |S|$ (the "marriage condition").

The Hungarian algorithm finds maximum-weight matchings in bipartite graphs in polynomial time.

New graphs can be constructed from existing ones:

Cartesian product $G \square H$: Vertices are pairs $(g,h)$ with $g \in V(G)$, $h \in V(H)$. Connect $(g_1,h_1)$ to $(g_2,h_2)$ if either $g_1 = g_2$ and $h_1h_2 \in E(H)$, or $h_1 = h_2$ and $g_1g_2 \in E(G)$.

Example: $P_m \square P_n$ is the $m \times n$ grid graph. $C_n \square K_2$ is the $n$-prism graph.

Tensor product $G \times H$: Connect $(g_1,h_1)$ to $(g_2,h_2)$ if $g_1g_2 \in E(G)$ AND $h_1h_2 \in E(H)$.

Graph join $G + H$: Disjoint union of $G$ and $H$ plus all edges between $G$ and $H$. Example: $K_2 + \bar{K_n} = K_{1,n}$ (star graph).