Graph Theory Basics

GRE Math Subject · Axiom Academy

Graphs, vertices, edges, paths, cycles, trees, and special graph properties A graph is a pair G = (V, E) where: V is a set of vertices (nodes) E is a set of edges (connections between vertices) Undirected: Edges have no direction; edge u,v = v,u Directed: Edges have direction; edge (u,v) ≠ (v,u) Weighted: Each edge has an associated numerical weight Simple: No multiple edges between same vertices, no self-loops V = A, B, C , E = A,B , A,C , B,C The degree of a vertex v, denoted deg(v) , is the number of edges incident to it. The sum of all degrees equals twice the number of edges (each edge contributes 2 to the total). Example: In the triangle graph: deg(A) = 2, deg(B) = 2, deg(C) = 2 Regular graph: All vertices have the same degree. Complete graph Kₙ : Every pair of distinct vertices is connected. Has [n choose 2] edges. A path is a sequence of vertices v₁, v₂, ..., vₖ where consecutive vertices are connected by edges. Length: Number of edges in the path = k - 1. Simple path: No repeated vertices (except possibly first and last). Cycle: A closed path where first and last vertex are the same, and no other vertices repeat. Distance: The shortest path length between two vertices u and v, denoted d(u,v) . Connected graph: There exists a path between every pair of vertices. Acyclic: A graph with no cycles. A tree is a connected, acyclic graph. Key properties of trees with n vertices: Unique simple path between any two vertices Removing any edge disconnects the graph

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