Cubic Graph — Definition, Formula & Examples

A cubic graph is a graph in which every vertex has exactly three edges connected to it. It is also called a 3-regular graph.

A cubic graph is a simple graph $G = (V, E)$ such that $\deg(v) = 3$ for every vertex $v \in V$ . Equivalently, it is a 3-regular graph, meaning the degree sequence is the constant sequence $(3, 3, \dots, 3)$ .

Key Formula

|E| = \frac{3\,|V|}{2}

Where:

$|E|$ = Number of edges in the cubic graph
$|V|$ = Number of vertices (must be even)

How It Works

To verify that a graph is cubic, check every vertex and confirm it has degree exactly 3. Because every vertex contributes degree 3, the Handshaking Lemma immediately tells you that the number of edges is

|E| = \frac{3|V|}{2}

, which forces the number of vertices to be even. Famous cubic graphs include the Petersen graph (10 vertices, 15 edges), the complete graph

K_4

(4 vertices, 6 edges), and the complete bipartite graph

K_{3,3}

(6 vertices, 9 edges).

Worked Example

Problem: Determine whether the complete graph K₄ is cubic, and find its number of edges using the cubic graph edge formula.

Step 1: In K₄, every vertex is adjacent to all 3 other vertices, so each vertex has degree 3.

\deg(v) = 3 \text{ for all } v \in V(K_4)

Step 2: Since every vertex has degree 3, K₄ is cubic. Apply the edge formula with |V| = 4.

|E| = \frac{3 \cdot 4}{2} = 6

Answer: K₄ is a cubic graph with 4 vertices and 6 edges.

Why It Matters

Cubic graphs appear throughout combinatorics and theoretical computer science. Tait's conjecture (later disproved) linked cubic planar graphs to the Four Color Theorem, and many NP-complete problems remain hard even when restricted to cubic graphs, making them a key testing ground for computational complexity.

Common Mistakes

Mistake: Assuming a cubic graph can have an odd number of vertices.

Correction: By the Handshaking Lemma, the sum of all degrees must be even. With every degree equal to 3, the vertex count 3|V| must be even, so |V| must be even.