Formal Definitions in Graph Theory

Core Idea

Graph theory formalizes the study of objects (vertices) and their pairwise relationships (edges). Directed and undirected graphs, simple graphs, multigraphs, and weighted graphs each have precise definitions capturing different relationship structures. Understanding these foundational distinctions is essential for all further work in graph theory.

How It's Best Learned

Study simple examples (friendship networks, web links, transportation systems) and verify which definition each satisfies. Draw both small examples and counterexamples to reinforce why each definition excludes certain structures.

Common Misconceptions

• Thinking all graphs must be simple graphs; multigraphs and directed graphs are equally fundamental.
• Confusing the direction of edges in directed graphs with temporal order.
• Believing that edge weights must always represent distance or cost.

Explainer

Graph theory's power comes from the precision of its definitions. An informal idea like "a network of connected things" is intuitive but imprecise — it doesn't tell you whether connections can be one-directional, whether two objects can have multiple distinct connections, or whether connections have strengths. The formal definitions fix all of these choices explicitly, and knowing which choice fits your problem is the first skill of applied graph theory.

The most fundamental object is a simple graph: a pair G = (V, E) where V is a finite set of vertices and E is a set of unordered pairs of distinct vertices. "Unordered" means edges are symmetric — if {u, v} ∈ E, then {v, u} is the same edge, not a separate one. "Distinct" means no vertex is connected to itself (no loops). "Set of pairs" means at most one edge between any two vertices. A simple graph captures symmetric, binary relationships between distinct objects — friendship, adjacency on a map, or reachability in a maze.

Relaxing the constraints yields richer models. A multigraph allows multiple edges between the same pair of vertices — useful when two cities have multiple direct flight routes, or two circuits have multiple parallel wires. A directed graph (or digraph) replaces unordered pairs with ordered pairs: edge (u, v) goes from u to v, but (v, u) is a separate edge in the other direction. Directed graphs model asymmetric relationships — web links (a page links to another, not necessarily vice versa), dependencies (A requires B, but B does not require A), or one-way streets. A weighted graph assigns a real number to each edge; this weight can represent distance, cost, capacity, probability, or any other quantity that characterizes the connection.

Each definition is a deliberate choice that shapes what questions you can ask. In a simple graph, you can ask "Is there a path from u to v?" In a weighted graph, you can ask "What is the shortest-weight path?" In a directed graph, you can ask "Is there a directed path from u to v?" — a question with a different answer than "from v to u?" The formal definition is not bureaucracy; it is the specification of the model. A theorem proven for simple graphs may fail for multigraphs, and a shortest-path algorithm designed for weighted graphs has no meaning on unweighted ones.

Getting comfortable with formal definitions in graph theory is preparation for rigorous mathematical argument. When you prove a theorem about graphs, you prove it about every graph satisfying the definition — not just the specific example you drew. That universality is what makes the definitions valuable. As you move to degree sequences, graph products, and structural theorems, these definitions will be the shared foundation that lets you apply general results to specific cases confidently.