A graph blow-up of a graph with vertices
,
, ...,
is a graph obtained by replacing
each vertex
by a nonempty independent
vertex set
and replacing each graph edge
by all the edges of the
complete bipartite graph with parts
and
, with no additional edges
(Illingworth 2022). Thus all vertices in a given
set
have the same graph neighborhood
outside that set. The natural map
from the blow-up to
sends every vertex of
to
, so
is the fiber over
.
If , the resulting graph is often denoted
. Its graph
order and edge count are
and
When all , the blow-up is called uniform and is denoted
by some authors. This exact-equality
case is also called a balanced blow-up (Hatami et al. 2014). It is the graph lexicographic product
, where
is the empty graph on
vertices.
When the graph order is fixed but is not necessarily
divisible by
, "balanced" is also used when the fiber
sizes differ by at most one (Avigad and Goldreich 2011).
Blow-ups of complete graphs are precisely the complete multipartite graphs. In particular, balanced blow-ups of complete graphs are Turán graphs.
This graph operation is distinct from algebraic blow-up and finite-time blow-up, and from the blow-up lemma, which concerns embedding graphs into regular pairs that approximate pairs of vertex sets inducing complete bipartite graphs in a graph blow-up.
Some graph-coloring literature instead replaces each original graph vertex by a nonempty clique. This clique-blowup convention, used in graph recoloring, differs from the independent vertex set replacement in the definition above.
Deleting selected edges from a blow-up gives a more general construction, since some pairs of parts need no longer induce complete bipartite graphs. Such a modified blow-up of the butterfly graph gives a counterexample to the conjectured graph triangle degree-sum bound of Bollobás and Erdős (Wouter CvB 2026).