Graph Theory

Graph theory is the mathematics of connection. Strip away the details of a road map, a friendship network, a molecule, or the internet, and what remains is the same skeleton: a set of things and the links between them. Graph theory studies that skeleton directly. Because so many different problems share this underlying shape, a single theorem about graphs can settle questions in logistics, chemistry, computer science, and epidemiology all at once.

What makes the subject so approachable is that its core objects are almost embarrassingly simple — dots and lines — yet they generate some of the deepest and most useful results in all of discrete mathematics. In this page we build the vocabulary (vertices, edges, degree), walk through paths, cycles, and trees, then trace the whole field back to the single puzzle that started it: whether the citizens of Königsberg could stroll across all seven of their bridges exactly once.

Learning Objectives

• Define a graph precisely in terms of vertices and edges, and read one from a drawing or a list.
• Compute the degree of a vertex and apply the Handshaking Lemma.
• Distinguish walks, paths, cycles, and trees, and recognize each in a picture.
• Explain the Seven Bridges of Königsberg and Euler's condition for an Euler path or circuit.
• Model real networks as graphs and reason about connectivity, routing, and structure.

Quick Answer

A graph $G = (V, E)$ is a set of vertices $V$ (the dots) together with a set of edges $E$ (the links joining pairs of vertices). The degree of a vertex is the number of edges touching it. A path is a route that never repeats a vertex; a cycle is a path that returns to its start; a tree is a connected graph with no cycles. Graph theory began in 1736 when Leonhard Euler proved that the Seven Bridges of Königsberg could not all be crossed exactly once — the answer depends only on the parity of the vertex degrees. Today graphs model everything from GPS routing to social networks to the structure of the web.

Where It Came From

In the 1700s the Prussian city of Königsberg (now Kaliningrad, Russia) sat on both banks of the Pregel River, which split around two islands. Seven bridges connected the four landmasses. A local pastime asked a deceptively casual question: could a person take a walk that crossed each of the seven bridges exactly once, returning (or not) to where they started? People had tried for years and failed, but failing to find a route does not prove one is impossible.

In 1736 Leonhard Euler, then at the St. Petersburg Academy, took the problem seriously — and in doing so invented an entirely new kind of mathematics. His crucial insight was that the shape of the city, the exact distances, the sizes of the islands, none of it mattered. All that mattered was which landmasses were connected to which, and by how many bridges. He collapsed each landmass to a single point and each bridge to a line between points. The map became a graph.

This was a genuinely radical move. Geometry up to that point was about measurement — lengths, angles, areas. Euler was studying a problem where measurement was irrelevant and only connection counted. He himself called it "the geometry of position" (geometria situs), and it seeded not just graph theory but also topology. His 1736 paper, Solutio problematis ad geometriam situs pertinentis, is universally regarded as the first paper in graph theory. The field lay relatively quiet for a century, then exploded in the 1800s and 1900s as electrical networks, chemistry (molecules are graphs of atoms and bonds), and eventually computer science each discovered they had been doing graph theory all along.

Vertices, Edges, and Degree

A graph is built from two ingredients:

• Vertices (also called nodes): the fundamental objects — cities, people, atoms, web pages.
• Edges (also called links): connections between pairs of vertices — roads, friendships, bonds, hyperlinks.

We write $G = (V, E)$. For example, with $V = \{A, B, C, D\}$ and edges $E = \{AB, BC, CA, CD\}$, vertex $C$ is connected to $A$, $B$, and $D$, while $D$ connects only to $C$.

The degree of a vertex, written $\deg(v)$, is the number of edges meeting it. In the example above:

$\deg(A) = 2, \quad \deg(B) = 2, \quad \deg(C) = 3, \quad \deg(D) = 1$

A vertex with degree $0$ is isolated; a vertex of degree $1$ (like $D$) is a leaf.

The Handshaking Lemma

Here is the first real theorem of graph theory, and it is beautiful. Add up the degrees of every vertex:

$\sum_{v \in V} \deg(v) = 2 + 2 + 3 + 1 = 8$

There are exactly $4$ edges, and $8 = 2 \times 4$. This is no accident. Every edge has two endpoints, so it contributes $1$ to the degree of each — a total of $2$ to the sum. Therefore:

$\sum_{v \in V} \deg(v) = 2 \, |E|$

This is the Handshaking Lemma: the sum of all degrees is always twice the number of edges. A famous corollary follows immediately — the number of odd-degree vertices is always even. (If you sum a bunch of numbers to an even total, an odd count of odd numbers is impossible.) The name comes from the observation that at any party, the total number of hands shaken is even, so the number of people who shook an odd number of hands must be even.

Worked example. A network has $10$ routers, each connected to exactly $3$ others. How many cables are there? The degree sum is $10 \times 3 = 30$, so $|E| = 30 / 2 = 15$ cables.

Walks, Paths, Cycles, and Trees

These four words describe how you move through a graph, and students constantly mix them up, so let us be precise.

• A walk is any sequence of edges you can traverse in order, repeats allowed: $A \to B \to C \to A \to C$ is a valid walk.
• A path is a walk with no repeated vertices: $A \to B \to C \to D$ is a path.
• A cycle is a path that returns to its starting vertex, closing a loop: $A \to B \to C \to A$.
• A graph is connected if there is a path between every pair of vertices.

Trees. A tree is a connected graph with no cycles. Trees are everywhere — family trees, file systems, decision trees, the hierarchy of a company. They have a signature property worth memorizing:

$|E| = |V| - 1$

A tree on $n$ vertices always has exactly $n - 1$ edges. Add one more edge anywhere and you necessarily create a cycle; remove any edge and the tree splits into two disconnected pieces. This makes trees the "leanest possible" connected graphs — the minimum wiring needed to link everything together, which is exactly why they underpin efficient network design.

Worked example. A company builds a communication network among $12$ offices so that every office can reach every other, using the fewest possible direct links. What structure should they use, and how many links? A tree is the minimum connected structure, so they need $12 - 1 = 11$ links. Any fewer and some office would be cut off; any more and there is redundancy.

The Seven Bridges of Königsberg

Now we can solve the founding problem. Label the four landmasses $A$ (north bank), $B$ (south bank), $C$ (east island), and $D$ (west island). Count the bridges touching each — these are the degrees. In the classic configuration:

$\deg(A) = 3, \quad \deg(B) = 3, \quad \deg(C) = 3, \quad \deg(D) = 5$

The total is $3 + 3 + 3 + 5 = 14$, which is twice the $7$ bridges — the Handshaking Lemma checks out.

A walk crossing every bridge exactly once is called an Euler path; if it also returns to the start it is an Euler circuit. Euler's genius was to notice a parity obstruction. Think about any landmass you pass through (not your start or end): every time you arrive by one bridge you must leave by a different one, so bridges are used up in pairs. That means an intermediate landmass needs an even number of bridges. Only the start and end vertices are allowed to have odd degree.

Euler's theorem, stated cleanly:

• An Euler circuit (start = end) exists exactly when the graph is connected and every vertex has even degree.
• An Euler path (start ≠ end allowed) exists exactly when the graph is connected and exactly zero or two vertices have odd degree.

In Königsberg, all four vertices have odd degree. Four is more than two, so no Euler path exists — full stop. The famous walk is impossible, and Euler proved it without trying a single route. This is the power of the abstraction: he replaced an exhausting search with a one-line count of parities.

Worked example. Suppose the city adds one bridge between $A$ and $B$. Now $\deg(A) = 4$ and $\deg(B) = 4$, while $C$ and $D$ still have $3$ and $5$. Exactly two odd-degree vertices ($C$ and $D$) remain, so an Euler path now does exist — it must start at one of $C, D$ and end at the other. One added bridge turns an impossible walk into a possible one.

Real-World Applications

• GPS and routing. Roads are edges, intersections are vertices, and finding the fastest route is a shortest-path problem (Dijkstra's algorithm) on a weighted graph. Every navigation app runs graph algorithms constantly.
• Social networks. People are vertices, friendships or follows are edges. Degree measures popularity; "friend suggestions" and community detection are graph-clustering problems; the "six degrees of separation" idea is a statement about path lengths.
• The internet and the web. Web pages are vertices and hyperlinks are directed edges. Google's original PageRank algorithm ranks pages purely from this link graph.
• Logistics and utilities. Delivery routes that must cover every street map directly onto the Königsberg problem (the "Chinese Postman" problem); laying minimum-cost cable or pipe is a minimum spanning tree problem, which is just finding the cheapest tree covering all vertices.
• Chemistry and biology. Molecules are graphs of atoms (vertices) and bonds (edges); protein-interaction and neural-connection maps are analyzed with the same tools.

Common Mistakes

1. Confusing a path with a walk. Students say "path" when they mean any route. A path has no repeated vertices. If your route revisits a vertex, it is a walk (or contains a cycle), not a path. Correction: check for repeats before calling something a path.

2. Thinking "no route was found" proves impossibility. Trying many walks across the bridges and failing proves nothing — you might have missed one. Correction: Euler's parity argument is a proof of impossibility because it rules out every possible walk at once. Reason about structure, not about failed attempts.

3. Misapplying the Euler condition. A common error is thinking an Euler circuit can exist with two odd vertices, or that any graph with all-even degrees has one. Both parts matter: the graph must also be connected, and for a circuit (returning to start) you need zero odd vertices, not two. Two odd vertices give a path but never a circuit. Correction: always check connectivity and count odd-degree vertices.

Comparison and Connections

Trees, paths, and cycles are all special kinds of graphs, and it helps to see them side by side.

Structure	Connected?	Contains a cycle?	Edges (on $n$ vertices)
Tree	Yes	No	$n - 1$
Path graph	Yes	No	$n - 1$
Cycle graph	Yes	Yes (one)	$n$
General connected graph	Yes	Maybe	$\geq n - 1$
Forest (disjoint trees)	No	No	$< n - 1$

A path graph is the simplest tree — a straight line of vertices. Add one edge joining its two ends and you get a cycle graph. Note the difference between an Euler path (uses every edge once) and a Hamiltonian path (visits every vertex once): despite the similar names they are very different problems — Euler's has an easy degree test, while deciding whether a Hamiltonian path exists is famously hard (NP-complete).

Practice Questions

Recall

State the Handshaking Lemma and give the formula relating the number of edges in a tree to its number of vertices.

Answer: The sum of all vertex degrees equals twice the number of edges: $\sum \deg(v) = 2|E|$. A tree on $n$ vertices has exactly $n - 1$ edges.

Understanding

A connected graph has degree sequence $2, 2, 2, 2$. Does it have an Euler circuit? What shape is it?

Answer: Every vertex has even degree and the graph is connected, so yes — an Euler circuit exists. Four vertices each of degree $2$ form a single cycle (a square), and you can traverse the loop once and return to start.

Application

A mail carrier must walk every street of a small neighborhood and return to the post office. The street map, as a graph, has exactly two intersections of odd degree. Can they do it without repeating any street?

Answer: Not as a closed route. With two odd-degree vertices there is an Euler path but not an Euler circuit, so they can cover every street once only if they may finish somewhere other than the start. To return to the post office they must repeat at least one street.

Analysis

Prove that in any graph the number of people who shook an odd number of hands is even.

Answer: By the Handshaking Lemma the total degree sum is $2|E|$, an even number. Split the sum into even-degree and odd-degree vertices. The even-degree terms sum to an even number, so the odd-degree terms must also sum to an even number. A sum of odd numbers is even only when there is an even count of them. Hence the number of odd-degree vertices is even. $\blacksquare$

FAQ

Is a single dot with no edges a graph? Yes. A graph can have vertices and no edges (an empty or edgeless graph), and even a single isolated vertex is a valid, if boring, graph.

What is the difference between directed and undirected graphs? In an undirected graph an edge $AB$ works both ways (like a two-way road or mutual friendship). In a directed graph (or digraph) edges have a direction, $A \to B$ (like one-way streets or Twitter "follows"). Everything on this page is undirected unless stated otherwise.

Can two vertices be joined by more than one edge? In a simple graph, no — at most one edge per pair and no self-loops. If you allow repeats you have a multigraph — and Königsberg is exactly a multigraph, since some landmasses are joined by two bridges.

Why couldn't people just find the Königsberg walk by trial and error? Because it doesn't exist, and no amount of trying can find something that isn't there. Euler's contribution was proving why it's impossible, which trial and error can never do.

Is graph theory the same as graphing equations? No — a common confusion caused by the shared word. "Graph" here means a network of vertices and edges, not the plot of a function like $y = x^2$. They are unrelated topics that happen to share a name.

Quick Revision

• A graph is $G = (V, E)$: vertices (dots) and edges (links).
• Degree = number of edges at a vertex. Handshaking Lemma: $\sum \deg(v) = 2|E|$; the count of odd-degree vertices is always even.
• Walk allows repeats; path has no repeated vertices; cycle is a closed path; tree is connected with no cycles and has $n - 1$ edges.
• Euler circuit ⟺ connected + all degrees even. Euler path ⟺ connected + exactly $0$ or $2$ odd-degree vertices.
• Königsberg has four odd-degree vertices ⟹ no Euler path. This 1736 proof by Euler founded graph theory.
• Applications: routing, social networks, PageRank, minimum spanning trees, molecules.

Related Topics

Prerequisites

• Discrete Mathematics overview

Related Topics

• Set theory (vertices and edges are just sets)
• Combinatorics (counting paths, trees, and colorings)

Next Topics

• Trees and spanning trees, graph coloring, and shortest-path algorithms
• Mathematics subject index