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 a set of edges $E$ connecting pairs of vertices
• Can be directed or undirected. In a directed graph, edges are ordered pairs (the direction matters). In an undirected graph, edges are unordered pairs (the connection goes both ways).
• Models relationships across domains. Social networks, transportation systems, molecular structures, and dependency chains all use graph representations.

One thing to keep straight: a simple graph has no loops (an edge from a vertex to itself) and no multiple edges between the same pair of vertices. Unless stated otherwise, most problems in discrete math assume simple graphs.

Vertex (Node)

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

Edge

• A connection between exactly two vertices representing the relationship or link being modeled
• Directed edges (also called arcs) go from one vertex to another; undirected edges work both ways
• Edges can be weighted, meaning they carry numerical values representing 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, degree splits into two parts. The in-degree $\deg^-(v)$ counts edges coming into $v$, and the out-degree $\deg^+(v)$ counts edges going out of $v$.
• The Handshaking Lemma is a fundamental counting tool: $\sum_{v \in V} \deg(v) = 2|E|$. Every edge contributes exactly 1 to the degree of each of its two endpoints, so the sum of all degrees is always twice the number of edges. A direct corollary: the number of vertices with odd degree must be even.

Adjacent Vertices

• Two vertices are adjacent if an edge connects them. They're also called neighbors.
• Adjacency defines local structure. Algorithms like BFS and DFS explore graphs by moving between adjacent vertices.
• The two primary data structures for representing graphs, adjacency matrices and adjacency lists, encode exactly this relationship. An adjacency matrix uses a $|V| \times |V|$ grid where entry $(i,j)$ is 1 if vertices $i$ and $j$ are adjacent. An adjacency list stores, for each vertex, the list of its neighbors.

---

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
• A simple path contains 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 of the graph.

Cycle

• A path that returns to its starting vertex, formally a path where $v_1 = v_k$ with at least 3 distinct edges
• A simple cycle repeats only the start/end vertex. Detecting cycles 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. Informally, the graph is "in one piece."
• A disconnected graph breaks into multiple components, which are maximal connected subgraphs with no edges between them.
• For directed graphs, connectivity comes in two flavors. A digraph is strongly connected if there's a directed path from every vertex to every other vertex. It's weakly connected if replacing all directed edges with undirected ones produces a connected graph.

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. This is what makes trees so structurally clean.
• Trees show up everywhere: file systems, parse trees, decision trees, and spanning trees all exploit this structure.

These three characterizations of a tree are all equivalent (for a graph on $n$ vertices): (1) connected and acyclic, (2) connected with exactly $n - 1$ edges, (3) acyclic with exactly $n - 1$ edges. Any two of {connected, acyclic, $n-1$ edges} imply the third.

---

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)$, meaning the edge goes from $u$ to $v$, not the reverse
• Models asymmetric relationships like web hyperlinks, prerequisite chains, one-way streets, and function calls
• Reachability becomes directional. You might be able to 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 depending on context
• Enables optimization problems. Shortest path (Dijkstra's algorithm), 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 distinct vertices is connected by an edge, 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 often serve as upper bounds in proofs.

Bipartite Graph

• Vertices partition into two disjoint sets where edges only connect vertices from different sets. No edge ever connects two vertices within the same set.
• A graph is bipartite if and only if it contains no odd-length cycles. This gives you a clean test: find an odd cycle and you've proven the graph isn't bipartite.
• Models two-class relationships like job assignments (workers and tasks), student-course enrollment, and matching problems. The complete bipartite graph $K_{m,n}$ connects every vertex in one set to every vertex in the other.

Planar Graph

• Can be drawn in the plane with no edge crossings. Such a drawing is called a plane embedding.
• Euler's formula applies: $V - E + F = 2$, where $F$ is the number of faces, including the outer unbounded face
• $K_5$ and $K_{3,3}$ are not planar. By Kuratowski's theorem, a graph is planar if and only if it contains no subgraph that is a subdivision of $K_5$ or $K_{3,3}$.

---

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 (one-to-one, onto mapping) between vertex sets that preserves adjacency. If $u$ and $v$ are adjacent in $G$, their images must be adjacent in $H$, and vice versa.
• Isomorphic graphs share all structural properties: identical vertex counts, edge counts, degree sequences, cycle lengths, etc.
• Proving isomorphism requires explicitly finding the mapping. Disproving it only requires finding one differing graph invariant (a property preserved under isomorphism, like degree sequence or number of cycles of a given length).

Here's a practical approach for checking isomorphism:

1. Compare $|V|$ and $|E|$. If they differ, the graphs aren't isomorphic.
2. Compare degree sequences (the sorted list of all vertex degrees). If they differ, not isomorphic.
3. Compare the number of cycles of each length, or other invariants like connectivity or chromatic number.
4. If all invariants match, try to construct an explicit bijection. Start by mapping vertices of the same degree to each other and check whether adjacency is preserved.

Matching invariants is necessary but not sufficient. Two non-isomorphic graphs can share the same degree sequence, edge count, and many other invariants. Only an explicit bijection proves isomorphism.

---

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 $C_4$ (cycle on 4 vertices). What's the same? What's different?

5. 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?