Graph Theory Terminology

Why This Matters

Graph theory sits at the heart of discrete mathematics because it gives you a visual and mathematical framework for modeling relationships—whether that's friendships on social media, routes between cities, or dependencies in a computer program. When you're tested on this material, you're not just being asked to define terms; you're being evaluated on whether you understand how graphs encode structure, what properties distinguish one graph type from another, and why certain configurations matter for algorithms and proofs.

The terminology here isn't arbitrary vocabulary—each term captures a specific structural property that determines what you can do with a graph. Can you traverse it efficiently? Does it contain redundant connections? Can you partition its vertices? Don't just memorize definitions—know what structural insight each term provides and how terms relate to each other. Master the connections, and proofs and algorithms will make much more sense.

---

Building Blocks: Vertices, Edges, and Basic Structure

Every graph reduces to two fundamental components and the rules governing how they connect. Understanding these primitives is essential because every other concept builds directly on them.

Graph

• A structure $G = (V, E)$ consisting of a set of vertices $V$ and edges $E$ connecting pairs of vertices
• Can be directed or undirected—directed graphs have ordered pairs as edges; undirected graphs have unordered pairs
• Models relationships across domains—social networks, transportation systems, molecular structures, and dependency chains all use graph representations

Vertex (Node)

• The fundamental unit representing an entity, object, or state in the system being modeled
• Cardinality notation $|V|$—the number of vertices determines graph size and affects complexity analysis
• Can carry attributes—in applications, vertices often store data like names, costs, or coordinates

Edge

• A connection between exactly two vertices—the relationship or link being modeled
• Directed edges (also called arcs) go from one vertex to another; undirected edges work both ways
• Can be weighted—numerical values on edges represent distances, costs, capacities, or probabilities

---

Measuring Connectivity: Degrees and Adjacency

How connected is a vertex? How do we describe the local neighborhood around a point? These concepts quantify the immediate structure around individual vertices.

Degree of a Vertex

• The count of edges incident to a vertex—written as $\deg(v)$ for vertex $v$
• In digraphs, splits into in-degree and out-degree—$\deg^-(v)$ counts incoming edges, $\deg^+(v)$ counts outgoing
• The Handshaking Lemma states $\sum_{v \in V} \deg(v) = 2|E|$—a fundamental counting tool for proofs

Adjacent Vertices

• Two vertices are adjacent if an edge connects them—also called neighbors
• Adjacency defines local structure—algorithms like BFS and DFS explore graphs by moving between adjacent vertices
• Adjacency matrices and lists—the two primary data structures for representing graphs encode exactly this relationship

---

Traversal Structures: Paths and Cycles

Moving through a graph requires understanding sequences of connected vertices. Paths and cycles are the building blocks for reachability, routing, and detecting structural properties.

Path

• A sequence of vertices $(v_1, v_2, \ldots, v_k)$ where each consecutive pair is connected by an edge
• Simple paths contain no repeated vertices—most algorithms seek simple paths to avoid redundancy
• Path existence determines reachability—if no path connects two vertices, they're in different components

Cycle

• A path that returns to its starting vertex—formally, a path where $v_1 = v_k$ with $k \geq 3$
• Simple cycles repeat only the start/end vertex—detecting them is crucial for many algorithms
• Cycle detection distinguishes trees from general graphs and identifies potential infinite loops in processes

---

Global Properties: Connectivity and Special Structures

Beyond local properties, graphs have global characteristics that determine their overall behavior. These properties affect whether algorithms can reach all vertices and what guarantees we can make about the structure.

Connected Graph

• Every pair of vertices has a path between them—the graph is "in one piece"
• Disconnected graphs have multiple components—separate subgraphs with no edges between them
• Connectivity is binary for undirected graphs but comes in degrees for directed graphs (strongly vs. weakly connected)

Tree

• A connected graph with no cycles—equivalently, a connected graph with exactly $|V| - 1$ edges
• Unique paths—between any two vertices in a tree, exactly one path exists
• Hierarchical applications—file systems, parse trees, decision trees, and spanning trees all exploit this structure

---

Directed and Weighted Variants

Standard graphs can be enhanced with direction and numerical values. These variants enable modeling of asymmetric relationships and optimization problems.

Directed Graph (Digraph)

• Edges are ordered pairs $(u, v)$—the edge goes from $u$ to $v$, not the reverse
• Models asymmetric relationships—web hyperlinks, prerequisite chains, one-way streets, function calls
• Reachability becomes directional—you might reach B from A but not A from B

Weighted Graph

• Each edge carries a numerical weight—written as $w(u, v)$ or $w(e)$
• Weights represent costs, distances, or capacities—context determines interpretation
• Enables optimization problems—shortest path (Dijkstra's), minimum spanning tree (Prim's, Kruskal's), and maximum flow all require weights

---

Special Graph Classes

Certain graph structures appear frequently enough to warrant their own names and specialized theorems. Recognizing these classes lets you apply known results instead of proving everything from scratch.

Complete Graph

• Every pair of vertices is connected—denoted $K_n$ for $n$ vertices
• Contains $\binom{n}{2} = \frac{n(n-1)}{2}$ edges—the maximum possible for a simple graph
• Every vertex has degree $n-1$—complete graphs are the "densest" simple graphs and serve as upper bounds in proofs

Bipartite Graph

• Vertices partition into two sets where edges only connect vertices from different sets
• Contains no odd-length cycles—this is both necessary and sufficient for bipartiteness
• Models two-class relationships—job assignments, student-course enrollment, matching problems

Planar Graph

• Can be drawn in the plane with no edge crossings—the drawing is called a plane embedding
• Euler's formula applies: $V - E + F = 2$—where $F$ is the number of faces including the outer infinite face
• $K_5$ and $K_{3,3}$ are not planar—Kuratowski's theorem says a graph is planar iff it contains no subdivision of these

---

Structural Equivalence: Isomorphism

When are two graphs "the same" despite looking different? Isomorphism captures structural identity independent of how vertices are labeled or drawn.

Isomorphic Graphs

• A bijection between vertex sets that preserves adjacency—if $u$ and $v$ are adjacent in $G$, their images must be adjacent in $H$
• Same structural properties—isomorphic graphs have identical vertex counts, edge counts, degree sequences, cycle structures, etc.
• Proving isomorphism requires finding the mapping; disproving it only requires finding one differing invariant

---

Quick Reference Table

---

Self-Check Questions

1. A graph has 6 vertices and 5 edges with no cycles. What type of graph must it be, and why?

2. Which two concepts both involve "no repeated vertices"—and how do they differ in what they describe?

3. You're given a graph and asked to prove it's not bipartite. What single structural feature would you look for?

4. Compare the degree sequence of $K_4$ (complete graph on 4 vertices) with that of a cycle $C_4$ (4 vertices in a cycle). What's the same? What's different?

5. FRQ-style: Given two graphs with the same number of vertices and edges, describe a systematic approach to determine whether they are isomorphic. What invariants would you check first, and why might matching invariants still not guarantee isomorphism?