Graph Theory Summary

Discrete Math · Axiom Academy

Let's review how graphs model relationships and networks, and how graph algorithms solve both practical and theoretical problems in computer science and mathematics. Definition: A graph G = (V, E) consists of vertices (nodes) and edges (connections between vertices) Types: Simple (no loops/multiedges), directed (edges have direction), weighted (edges have values), multigraph (multiple edges allowed) Degree: Number of edges incident to a vertex. In directed graphs, distinguish in-degree and out-degree Representations: Adjacency matrix (space O(V²)), adjacency list (space O(V + E)), or visual diagram Complete Graph Kₙ : Every vertex connected to every other vertex; has n(n-1)/2 edges Bipartite Graph: Vertices can be divided into two sets with edges only between sets; useful for matching problems Tree: Connected acyclic graph with exactly n-1 edges for n vertices; unique path between any two vertices Planar Graph: Can be drawn without edge crossings; satisfies Euler's formula: V - E + F = 2 Path: Sequence of vertices where consecutive vertices are connected by edges; length is number of edges Cycle: Path that starts and ends at same vertex without repeating edges Connected: Path exists between every pair of vertices; components are maximal connected subgraphs Eulerian Path/Circuit: Path/circuit using every edge exactly once; exists if graph has 0 or 2 odd-degree vertices

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