A cubic graph is a graph where every vertex (point) connects to exactly three edges (lines). In formal terms, it’s a “3-regular” graph, meaning every vertex has the same degree of 3. This simple definition leads to a surprisingly rich class of graphs that show up across mathematics, computer science, and even chemistry.
The Basic Definition
In graph theory, a “regular” graph is one where every vertex has the same number of connections. A graph where every vertex connects to exactly one edge is trivial, and two connections per vertex just gives you simple cycles (loops). Three connections per vertex is where things get interesting, which is why cubic graphs have their own name and a long history of study.
Because every vertex has exactly three edges, cubic graphs follow a simple counting rule: if the graph has n vertices, it has exactly 3n/2 edges. This means cubic graphs can only exist with an even number of vertices. You can’t build one with, say, 7 vertices because you’d end up with a fractional number of edges.
Well-Known Cubic Graphs
Several famous graphs in mathematics are cubic. The simplest is K4, the complete graph on four vertices, which looks like a tetrahedron where every corner connects to every other corner. The cube graph Q3 (the skeleton of a three-dimensional cube) is another natural example: each of its 8 corners meets exactly 3 edges.
The Petersen graph, with 10 vertices and 15 edges, is one of the most studied objects in all of graph theory. It serves as a counterexample to many conjectures and has a beautiful symmetric structure that can be embedded on a projective plane with six pentagonal faces. K3,3, the complete bipartite graph with two groups of three vertices, is another classic. It plays a starring role in proving which graphs can be drawn on a flat surface without crossing edges.
Only five connected cubic graphs are “symmetric” (meaning they look the same from every vertex and every edge) with short cycles: K4, K3,3, the cube graph, the Petersen graph, and the dodecahedral graph.
Coloring Properties
Graph coloring asks: how few colors do you need to label vertices (or edges) so that no two adjacent ones share a color? Cubic graphs have clean answers to both versions of this question.
For vertex coloring, Brooks’ Theorem tells us that any connected cubic graph can be colored with at most 3 colors, unless it’s the complete graph K4 (which needs 4). This is a tight bound because many cubic graphs genuinely require all 3 colors.
For edge coloring, Vizing’s Theorem says any cubic graph needs either 3 or 4 colors to color its edges so that no two edges sharing a vertex get the same color. The distinction between 3 and 4 connects to deeper structural questions. A planar cubic graph (one that can be drawn flat without crossings) can always be 3-edge-colored as long as it has no “bridge,” an edge whose removal would split the graph into disconnected pieces. This result ties directly to the Four Color Theorem: in 1880, the mathematician Peter Guthrie Tait showed that proving every bridgeless planar cubic graph is 3-edge-colorable would be equivalent to proving the Four Color Theorem itself.
Bridges and Connectivity
A bridge in a graph is a single edge that, if removed, disconnects part of the graph from the rest. Bridgeless cubic graphs, those without any such weak link, have especially nice properties. For cubic graphs specifically, being connected and bridgeless is the same as being 2-connected, meaning you’d need to remove at least two vertices to disconnect the graph.
This distinction matters because many theorems about cubic graphs only hold when bridges are absent. The 3-edge-coloring result mentioned above is the most famous example: a planar cubic graph with a bridge cannot be 3-edge-colored, but remove the possibility of bridges and the coloring always works.
Hamiltonian Cycles and Tait’s Conjecture
A Hamiltonian cycle is a path that visits every vertex exactly once and returns to the start. In 1880, Tait conjectured that every cubic polyhedral graph (a 3-connected planar cubic graph) contains a Hamiltonian cycle. If true, this would have provided another proof of the Four Color Theorem.
It took over 60 years, but William Tutte refuted the conjecture in 1946 with a counterexample on 46 vertices, now called the Tutte graph. The smallest possible counterexample turned out to be the Barnette-Bosák-Lederberg graph on 38 vertices, which was later proved minimal. Researchers have since cataloged a series of non-Hamiltonian cubic polyhedral graphs ranging from 38 to 124 vertices. The question of which cubic graphs contain Hamiltonian cycles remains an active area of study.
Cubic Graphs in Chemistry
Cubic graphs have a natural connection to molecular chemistry, most notably through fullerenes. Fullerenes are cage-shaped carbon molecules (the most famous being the soccer-ball-shaped C60, or “buckyball”) where every carbon atom bonds to exactly three neighbors. This three-bond structure means the molecular skeleton of every fullerene is a planar cubic graph.
More specifically, fullerene graphs are cubic, planar, and 3-connected, with faces that are exclusively pentagons and hexagons. Every fullerene has exactly 12 pentagonal faces (a result known as the 12 Pentagon Theorem) and a variable number of hexagons. The mathematical properties of cubic graphs, including their coloring and connectivity results, translate directly into predictions about molecular stability and electronic structure. This connection between pure graph theory and physical chemistry has made cubic graphs an important tool in computational molecular science.
Why Cubic Graphs Matter
Cubic graphs occupy a sweet spot in graph theory. They’re structured enough to have strong theorems apply to them, but complex enough to exhibit rich and sometimes surprising behavior. Many problems that are computationally hard for general graphs remain hard even when restricted to cubic graphs, which makes them important test cases in theoretical computer science. At the same time, their regularity makes them more tractable than arbitrary graphs for proving new results. When graph theorists want to test a conjecture or look for counterexamples, cubic graphs are often the first place they look.