Graphs and Trees

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 = $2\|E\|$
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 $\sum \deg(v) = 2|E|$ because each edge connects two endpoints. Corollary: odd-degree vertices are always even in number.

Every edge lights two counters at once --- which is the whole lemma

Trees & Pitfalls

A tree is a special graph defined as connected and acyclic. On $n$ vertices, a tree has exactly $n-1$ edges and a unique path between any two nodes.

Graph Type	Connected?	Acyclic?	Edge Count
Tree	Yes	Yes	$n - 1$
Forest	No	Yes	$< n - 1$
Cycle Graph	Yes	No	$n$

Common Pitfall: Forgetting that $\sum \deg(v)$ equals twice the edges, not $|E|$ alone. A tree must be both connected and acyclic; disconnected acyclic graphs are forests.

Modeling Connections

Trees & Pitfalls

Practise this lesson

Discrete Mathematics