# Graph Theory

**Type:** Concept  
**Domain:** Discrete Mathematics  
**Founding problem:** Königsberg Bridge Problem, Euler, 1736  
**Codex URL:** /mathematics/discrete/graph-theory/  
**Entry status:** Live — v1.0 (2026-05-27)

## Summary
Studies networks of vertices connected by edges. Founded by Euler's 1736 solution to the Königsberg Bridge Problem.

## Key terminology
Degree, path, cycle, connected graph, tree, planar graph

## Euler's theorem
An Eulerian path exists iff a graph has exactly 0 or 2 vertices of odd degree. Königsberg's graph had 4 odd-degree vertices — no such walk possible.

## Handshake Lemma
Sum of all vertex degrees = 2×(number of edges). Number of odd-degree vertices is always even.

## Key algorithms
- Dijkstra's algorithm (1956) — shortest path
- Kruskal's/Prim's algorithms — minimum spanning tree
- Applications: PageRank, GPS routing, social networks

## Scale-free networks
Barabási-Albert (1999): preferential attachment explains power-law degree distributions in real-world networks.

## Sources
### Tier 1
- West, D.B. (2001). *Introduction to Graph Theory*. 2nd ed.
- Euler, L. (1736). Solutio problematis ad geometriam situs pertinentis.
### Tier 2
- Barabási, A-L. and Albert, R. (1999). Emergence of scaling in random networks. *Science*.
### Tier 3
- Hopkins, B. and Wilson, R.J. (2004). The truth about Königsberg. *College Math Journal*.

---
*Mathematics Codex entry v1.0 — added 2026-05-27 — thecodex.expert/mathematics/*