Graphs and Trees

Graphs model objects as vertices and connections as edges. Most beginner mistakes come from miscounting degree or confusing paths with edges.

A graph is bipartite when its vertices can be split into two groups so every edge goes across the split. Odd cycles are the main obstruction.

Euler questions ask whether you can use every edge exactly once. The degree pattern tells you the answer quickly.

A rooted tree picks one vertex as the root, which gives every other vertex a parent-child relationship and a level.

A tree is a connected graph with no cycles. In a tree with n vertices, the number of edges is always n-1.