A graph $G = (V, E)$ consists of a set of vertices $V$ and a set of edges $E \subseteq V \times V$. Graphs model relationships — networks, maps, dependencies — and are central to discrete mathematics, computer science, and topology.
Degree: The degree $\deg(v)$ of a vertex is the number of edges incident to it.
By the Handshaking Lemma, $\sum_{v \in V} \deg(v) = 2|E|$.
Path: A sequence of distinct vertices $v_0, v_1, \ldots, v_k$ where each
consecutive pair is connected by an edge.
Connected: A graph is connected if there is a path between every pair of vertices.
Two fundamental ways to traverse a graph from a starting vertex:
- Breadth-First Search (BFS): Explore all neighbors at distance $k$ before distance $k+1$. Uses a queue. Finds shortest paths.
- Depth-First Search (DFS): Follow one path as deep as possible before backtracking. Uses a stack (or recursion). Reveals connected components and cycles.
Instructions: Click an empty spot to add a vertex. Click two vertices in sequence to add an edge. Then pick a traversal and click a start vertex.