Graph Theory Formula Sheet

Math for CS · Axiom Academy

FORMULA SHEET Graph Theory Reference Essential formulas, properties, and complexity results The sum of all vertex degrees equals twice the number of edges. Consequence: the number of odd-degree vertices is always even. Euler's Formula (Planar Graphs) For any connected planar graph with vertices, edges, and faces (including the outer face). Derived from Euler's formula. If the graph has no triangles: . A graph with vertices is a tree if and only if any two of these hold (the third follows): Number of Labeled Trees (Cayley's Formula) The number of distinct labeled trees on vertices. For example, . Every vertex connects to every other. Degree of each vertex: . Every vertex in one partition connects to every vertex in the other. The chromatic number is at most one more than the maximum degree (Brook's theorem gives unless is a complete graph or an odd cycle). Euler circuit exists iff every vertex has even degree and the graph is connected. Euler path exists iff exactly 0 or 2 vertices have odd degree and the graph is connected. Quick reference: A tree on vertices has edges. A complete graph has edges. The sum of degrees always equals . BFS and DFS both run in .

This is the written version of the interactive lesson above. See the full Math for CS course.