Graph Theory Basic Definitions Reference Cheat Sheet

A printable reference covering vertices, edges, degree, paths, cycles, connectedness, trees, complete graphs, and bipartite graphs for grades 10-12.

TopicsGraphs Algorithms Counting Study Guide Mathematics

Download PNG

Related Tools

Related Infographics

Study as Flashcards

Math Vocabulary

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.

Sign in to save