Graph Theory Basic Definitions Reference Cheat Sheet

Graph theory studies networks made of vertices and edges, such as maps, social networks, circuits, and scheduling problems. This cheat sheet summarizes the basic definitions students need before solving graph theory problems. It helps students quickly distinguish structures like paths, cycles, trees, and complete graphs.

These ideas are important because many advanced counting, optimization, and computer science problems use graph models.

The most important quantities are the number of vertices $|V|$ , the number of edges $|E|$ , and the degree $\deg(v)$ of each vertex. The Handshaking Lemma says $\sum_{v \in V} \deg(v) = 2|E|$ , which connects local vertex information to the whole graph. Special graph families have useful formulas, such as $|E| = n - 1$ for a tree with $n$ vertices and $|E| = \frac{n(n-1)}{2}$ for a complete graph $K_n$ .

Understanding whether a graph is connected, simple, directed, weighted, or bipartite is the first step in choosing the right method.

Key Facts

A graph is usually written as $G = (V,E)$ , where $V$ is the set of vertices and $E$ is the set of edges.
The degree of a vertex $v$ , written $\deg(v)$ , is the number of edges incident to $v$ , with a loop counting twice in an undirected graph.
The Handshaking Lemma states that $\sum_{v \in V} \deg(v) = 2|E|$ for any finite undirected graph.
A simple graph has no loops and no multiple edges between the same pair of vertices.
A path is a sequence of distinct vertices connected by edges, while a cycle is a path that starts and ends at the same vertex with no repeated internal vertices.
A connected graph has a path between every pair of vertices, and its connected components are the largest connected subgraphs.
A tree is a connected graph with no cycles, so a tree with $n$ vertices has exactly $n - 1$ edges.
A complete graph $K_n$ has every pair of distinct vertices connected by an edge, so it has $|E| = \frac{n(n-1)}{2}$ edges.

Vocabulary

Vertex: A vertex is a point or node in a graph, and the set of all vertices is usually written as $V$ .
Edge: An edge is a connection between two vertices, and the set of all edges is usually written as $E$ .
Degree: The degree $\deg(v)$ of a vertex $v$ is the number of edges touching that vertex, with loops counted twice in undirected graphs.
Connected Graph: A connected graph is a graph in which every pair of vertices has at least one path between them.
Tree: A tree is a connected graph with no cycles, and a tree with $n$ vertices has $n - 1$ edges.
Bipartite Graph: A bipartite graph has vertices split into two sets so that every edge connects a vertex in one set to a vertex in the other set.

Common Mistakes to Avoid

Confusing vertices with edges is wrong because vertices are the objects or nodes, while edges are the connections between them.
Counting a loop as one toward degree is wrong in an undirected graph because a loop touches the same vertex twice, so it contributes $2$ to $\deg(v)$ .
Using $|E| = n - 1$ for every connected graph is wrong because that formula applies only to trees, not to connected graphs with cycles.
Assuming a graph is connected because most vertices are linked is wrong because connected means every pair of vertices must have a path between them.
Forgetting to divide by $2$ in the Handshaking Lemma is wrong because $\sum_{v \in V} \deg(v)$ counts each undirected edge twice.

Practice Questions

1 A graph has vertex degrees $3, 3, 2, 2, 2, 0$ . Use $\sum_{v \in V} \deg(v) = 2|E|$ to find $|E|$ .
2 How many edges are in the complete graph $K_8$ ? Use $|E| = \frac{n(n-1)}{2}$ .
3 A connected graph has $12$ vertices and $11$ edges. If it has no cycles, what graph family is it?
4 Explain why a graph containing a triangle cannot be bipartite.

Understanding Graph Theory Basic Definitions Reference

A graph becomes more useful when each vertex has a clear meaning. In a road map, vertices may represent intersections and edges may represent roads. In a class timetable, vertices can represent courses, with an edge showing that two courses have students in common.

The meaning of an edge matters. An edge might show physical contact, permission to travel, similarity, or a dependency.

Before doing any calculation, state what the vertices represent and what it means for two vertices to be joined. This prevents a correct graph calculation from answering the wrong real-world problem.

Degrees give a quick way to inspect the shape of a network. A vertex with degree zero is isolated. It has no direct connection to the rest of the graph.

A vertex with a very large degree may be a hub, such as a busy airport or a popular account in a social network. Adding all degrees is a useful error check when drawing a graph. Every ordinary edge contributes one to the degree at each of its ends, so the total must be even.

This means that the number of odd-degree vertices is always even. That fact can reveal a missing edge in a diagram or rule out an impossible degree list.

Students often need to separate a walk, a trail, and a path. A walk may repeat vertices or edges. A trail does not repeat an edge.

A path avoids repeated vertices. The exact definition used by a textbook can vary slightly, so read the instructions carefully. Cycles are especially important because they show that there is more than one way around part of a network.

In a transport system, a cycle can provide an alternate route after a road closure. In a dependency diagram, a cycle can signal a problem, since each task may be waiting for another task in the same loop.

An edge whose removal increases the number of connected components is called a bridge. Bridges mark fragile connections.

Trees are networks with no redundant loop. Between any two vertices in a tree, there is exactly one path. This makes trees useful for organizing folders, family relationships, tournament brackets, and minimum-cost connection plans.

If an extra edge is added to a tree, it creates exactly one cycle. If any edge is removed, the tree becomes disconnected. A spanning tree keeps every vertex of a connected graph while using only enough edges to maintain connection.

Bipartite graphs offer another test based on structure rather than counting. Their vertices can be split into two groups, with every edge going between groups. A graph is bipartite exactly when it has no odd cycle.

This helps model matching problems, such as assigning students to projects or workers to shifts. Complete graphs represent every possible pairwise link, so their edge count grows very quickly as the number of vertices grows.

Sign in to save