Modeling Connections
A graph is a set of vertices joined by edges, modeling anything from road maps to social networks.
| Term | Definition | Example / Rule |
|---|---|---|
| Degree | Incident edges on a vertex | Sum of degrees = |
| Path | Sequence of connected vertices | Can lead to a cycle |
| Connected | Path exists between all pairs | Isolated nodes disconnect it |
| Directed | One-way edges (digraph) | Unlike undirected edges |
The handshaking lemma states because each edge connects two endpoints. Corollary: odd-degree vertices are always even in number.
Trees & Pitfalls
A tree is a special graph defined as connected and acyclic. On vertices, a tree has exactly edges and a unique path between any two nodes.
| Graph Type | Connected? | Acyclic? | Edge Count |
|---|---|---|---|
| Tree | Yes | Yes | |
| Forest | No | Yes | |
| Cycle Graph | Yes | No |
Common Pitfall: Forgetting that equals twice the edges, not alone. A tree must be both connected and acyclic; disconnected acyclic graphs are forests.