‹
🧮
Graph Theory
· Formula🧮 Formula Reference Sheet
Graph G = (V, E): vertices V and edges E Degree: edges incident to a vertex Handshake lemma: Σ deg(v) = 2|E| Tree: connected, no cycles N-vertex tree has N−1 edges Eulerian circuit: every edge once → all degrees even
⚡ Example per formula
Graph G = (V, E): vertices V and edges E
↳V={A,B,C}, E={AB, BC} → 3 vertices, 2 edges
Degree: edges incident to a vertex
↳A connected to B,C → deg(A)=2
Handshake lemma: Σ deg(v) = 2|E|
↳Σ deg = 2|E|: triangle → 2+2+2 = 6 = 2×3
Tree: connected, no cycles
↳4 vertices in a tree → exactly 3 edges
N-vertex tree has N−1 edges
↳10 vertices → 9 edges
Eulerian circuit: every edge once → all degrees even
↳all degrees even → Eulerian circuit exists
✏️
Practice Exercises →
5 graded problems · AI checks each step