Graph Operations: Building New Graphs from Old Ones

Introduction

Numbers have arithmetic: add two numbers, multiply them, subtract one from another — and you get a new number. Graphs have their own arithmetic too. Given one or two graphs, graph theorists have defined precise operations that produce entirely new graphs with predictable, useful properties.

These operations are not just mathematical curiosities. The complement underlies Ramsey theory and independent sets. The join constructs wheel graphs. The line graph transforms edge problems into vertex problems. The Cartesian product builds the hypercube — a structure at the heart of parallel computing, coding theory, and network design.

In this post we cover the five most important graph operations, with visual examples for each.

1. The Complement

Definition

Definition: The complement of a graph $G$, written $\overline{G}$ (or $G^c$), is the graph on the same vertex set where two vertices are adjacent in $\overline{G}$ if and only if they are not adjacent in $G$.

The rule is simple:
- Every edge of $G$ → delete it from $\overline{G}$
- Every non-edge of $G$ → add it to $\overline{G}$

Example

Consider $G$ with 5 vertices $\{A,B,C,D,E\}$ and 5 edges:

Now swap every edge for a non-edge and vice versa:

The original edges (orange) disappear; the former non-edges (teal) become the new edges of $\overline{G}$.

The Fundamental Property

Theorem: $G \cup \overline{G} = K_n$ (the complete graph on $n$ vertices).

Placing $G$ on top of $\overline{G}$ always yields $K_n$, because every pair of vertices is either an edge in $G$ or an edge in $\overline{G}$ — never both, never neither. There is no overlap and no gap.

Consequences:
- $|E(G)| + |E(\overline{G})| = \binom{n}{2}$ — the edge counts are complementary
- $\overline{\overline{G}} = G$ — the complement of the complement is the original graph
- If $G \cong \overline{G}$, the graph is called self-complementary (e.g. $P_4$, $C_5$)

Connection to Independent Sets

A clique in $G$ (every pair connected) corresponds to an independent set in $\overline{G}$ (no pair connected), and vice versa. This symmetry is the foundation of Ramsey theory:

$$\omega(G) = \alpha(\overline{G}) \qquad \alpha(G) = \omega(\overline{G})$$

2. The Union

Definition

Definition: The union of graphs $G$ and $H$, written $G \cup H$, is the graph whose vertex set is $V(G) \cup V(H)$ and whose edge set is $E(G) \cup E(H)$.

When $G$ and $H$ are vertex-disjoint (share no vertices), the union is simply both graphs placed side-by-side on the same page with no connections between them. The result is always a disconnected graph with (at least) two components.

Example

Let $G = K_3$ (a triangle) and $H = C_4$ (a 4-cycle square). Their union:

The orange triangle ($K_3$) and the teal square ($C_4$) coexist on the same graph but share no vertices or edges — two completely separate components.

Notation for Multiple Copies

The disjoint union of $k$ copies of $G$ is written $kG$:

$$2K_3 = K_3 \cup K_3 \quad \text{(two disjoint triangles)}$$

This notation appears frequently in graph theory: “$G$ contains $2K_2$ as a subgraph” means $G$ has two disjoint edges with no shared endpoints — a matching of size 2.

3. The Join

Definition

Definition: The join of graphs $G$ and $H$, written $G \vee H$, starts as their union but then adds a new edge from every vertex of $G$ to every vertex of $H$.

If $|V(G)| = m$ and $|V(H)| = n$, the join adds exactly $m \times n$ new edges on top of the union.

Example: Building the Wheel Graph

The wheel graph $W_n = K_1 \vee C_n$ is the classic application of the join.

Take $K_1$ (a single hub vertex) and $C_5$ (a 5-cycle ring). Their join connects the hub to every ring vertex:

The orange hub (from $K_1$) gains edges to all 5 teal ring vertices (from $C_5$), producing the spokes. The ring edges remain. The result is $W_5$ — a wheel with 5 spokes.

General formula for $K_1 \vee C_n$:
- Vertices: $n + 1$
- Edges: $n$ (ring) $+ n$ (spokes) $= 2n$

Other Join Examples

The second row is important: joining two independent sets (no edges) produces the complete bipartite graph — every vertex on one side connects to every vertex on the other side.

4. The Line Graph

Definition

Definition: The line graph $L(G)$ of a graph $G$ is constructed as follows:
- For every edge $e \in E(G)$, create a new vertex $v_e$ in $L(G)$
- Two vertices $v_e$ and $v_f$ in $L(G)$ are adjacent if and only if the corresponding edges $e$ and $f$ share an endpoint in $G$

The line graph transforms an edge-focused problem into a vertex-focused one. Questions about edges in $G$ become questions about vertices in $L(G)$.

Intuition

Imagine placing a new dot at the midpoint of every road (edge). Two midpoint-dots are connected in the line graph if their roads share a junction (vertex). The midpoint network is $L(G)$.

Example

Let $G$ be a graph with 4 vertices $\{A,B,C,D\}$ and 5 edges $\{AB, BC, CD, AC, BD\}$:

Each edge becomes a vertex in $L(G)$. Two new vertices connect if their edges shared an endpoint in $G$:

The 5 edges of $G$ became 5 colored vertices of $L(G)$, connected by 8 edges. The only two non-edges are $AB$–$CD$ (disjoint vertex sets $\{A,B\}$ vs $\{C,D\}$) and $AC$–$BD$ (disjoint $\{A,C\}$ vs $\{B,D\}$).

Key Properties of Line Graphs

• $|V(L(G))| = |E(G)|$
• $|E(L(G))| = \frac{1}{2} \sum_{v \in G} \deg(v)^2 - |E(G)|$
• If $G$ is Eulerian (every vertex has even degree), then $L(G)$ is Hamiltonian
• Whitney’s theorem: If $|V(G)| \geq 5$, then $L(G) \cong L(H)$ implies $G \cong H$ (line graphs are almost uniquely invertible)

Why Line Graphs Matter

The line graph is a bridge between two different languages for describing the same structure.

5. The Cartesian Product

Definition

Definition: The Cartesian product of graphs $G$ and $H$, written $G \,\square\, H$, is the graph where:
- Vertices: All ordered pairs $(g, h)$ where $g \in V(G)$ and $h \in V(H)$
- Edges: Two vertices $(g_1, h_1)$ and $(g_2, h_2)$ are adjacent if and only if either:
- $g_1 = g_2$ and $h_1 h_2 \in E(H)$, or
- $h_1 = h_2$ and $g_1 g_2 \in E(G)$

In plain English: two pairs are adjacent when they differ in exactly one coordinate, and that difference is an edge in the corresponding graph.

Size facts:
- $|V(G \,\square\, H)| = |V(G)| \cdot |V(H)|$
- $|E(G \,\square\, H)| = |E(G)| \cdot |V(H)| + |V(G)| \cdot |E(H)|$

Example A: Grid Graph $P_4 \,\square\, P_3$

Let $G = P_4$ (path on 4 vertices: $v_1\text{-}v_2\text{-}v_3\text{-}v_4$) and $H = P_3$ (path on 3 vertices: $w_1\text{-}w_2\text{-}w_3$).

The product $P_4 \,\square\, P_3$ has $4 \times 3 = 12$ vertices — each $(v_i, w_j)$ pair:

Reading the grid: The 4 columns are the 4 copies of $P_3$ (one per vertex of $P_4$). The 3 rows are the 3 copies of $P_4$ (one per vertex of $P_3$). Horizontal edges come from $P_4$’s edges; vertical edges come from $P_3$’s edges.

Verify the edge count: $|E(P_4)| \cdot |V(P_3)| + |V(P_4)| \cdot |E(P_3)| = 3 \times 3 + 4 \times 2 = 9 + 8 = 17$ edges. Count them in the grid: 3 rows of 3 horizontal edges = 9, plus 4 columns of 2 vertical edges = 8. ✓

Example B: Hypercubes $Q_n = K_2 \,\square\, K_2 \,\square\, \cdots$

The most celebrated application of the Cartesian product is the family of hypercubes. Start with $K_2$ — a single edge between vertices $\{0, 1\}$ — and keep multiplying:

$Q_1 = K_2$: Two vertices, one edge. (A line segment in 1D.)

$Q_2 = K_2 \,\square\, K_2$: Four vertices $\{00, 01, 10, 11\}$, four edges. Two vertices are adjacent iff their binary labels differ in exactly one bit.

$Q_3 = Q_2 \,\square\, K_2$: Eight vertices (3-bit binary strings), twelve edges. This is the familiar 3D cube — adjacent vertices differ in exactly one bit.

The pattern: $Q_n$ has $2^n$ vertices (all $n$-bit binary strings) and $n \cdot 2^{n-1}$ edges. Two vertices are adjacent if and only if their binary labels differ in exactly one position (Hamming distance 1).

Commutativity and Associativity

Note: $G \,\square\, H \cong H \,\square\, G$ (the product is commutative up to isomorphism).
The Cartesian product is also associative: $(G \,\square\, H) \,\square\, K \cong G \,\square\, (H \,\square\, K)$.

This is why we can write $Q_3 = K_2 \,\square\, K_2 \,\square\, K_2$ without specifying parenthesisation.

Comparing the Five Operations

Practice Problems

Problem 1: Computing a Complement

Question: Graph $G$ has vertices $\{1,2,3,4\}$ and edges $\{12, 13, 24\}$. List the edges of $\overline{G}$.

Problem 2: Self-Complementary Graph

Question: Show that $P_4$ (the path $1\text{-}2\text{-}3\text{-}4$) is self-complementary — i.e. $P_4 \cong \overline{P_4}$.

Problem 3: Line Graph

Question: Compute $L(G)$ where $G = K_3$ (triangle with vertices $\{A,B,C\}$ and edges $\{AB,BC,CA\}$).

Problem 4: Cartesian Product Edge Count

Question: Compute $|E(C_3 \,\square\, K_2)|$ using the formula. What well-known graph is the result?

Problem 5: Join and Complete Bipartite

Question: Prove that $\overline{K_m} \vee \overline{K_n} \cong K_{m,n}$.

Problem 6: Hypercube Properties

Question: (a) How many vertices and edges does $Q_5$ have? (b) What is the degree of every vertex in $Q_n$?

Applications

Chip Design and Parallel Computing (Hypercubes)

Hypercube $Q_n$ networks were the dominant parallel computer architecture in the 1980s–90s (nCUBE, Intel iPSC). With $2^n$ processors as vertices, any two processors that differ in one bit can communicate directly. The diameter of $Q_n$ is $n$ (at most $n$ hops between any pair), and its high symmetry enables efficient routing algorithms. Today, hypercube topologies survive in GPU interconnect and distributed memory systems.

Coding Theory (Hypercubes and Hamming Distance)

The vertices of $Q_n$ are all $n$-bit binary codewords. Two codewords are adjacent in $Q_n$ iff their Hamming distance is 1. A binary error-correcting code of minimum distance $d$ corresponds to an independent set in $Q_n^{(d-1)}$ (the $(d-1)$-th power of $Q_n$). The design of efficient codes is directly tied to the combinatorics of hypercube subgraphs.

Social Network Analysis (Complement)

The complement of a social network is the “non-relationship” graph — useful for studying what connections are absent. Complement analysis reveals structural holes (people who could bridge communities but don’t), which is a key metric in social capital theory. Finding large cliques in $G$ (friend groups) is equivalent to finding large independent sets in $\overline{G}$.

Scheduling and Edge Colouring (Line Graphs)

A classic scheduling problem: given a set of tasks, each requiring a shared machine for one time slot, assign time slots to tasks so no machine is double-booked. This is exactly edge colouring of the conflict graph $G$ — which equals vertex colouring of $L(G)$. Vizing’s theorem (that $\chi'(G) \leq \Delta(G) + 1$) was originally proved by analysing line graphs.

Transport Networks (Cartesian Product)

Grid street networks, printed circuit board routing layers, and multi-dimensional mesh networks are all Cartesian products in disguise. A $p \times q$ city grid is $P_p \,\square\, P_q$. A 3D mesh supercomputer topology is $P_a \,\square\, P_b \,\square\, P_c$. The Cartesian product’s diameter is $\text{diam}(G) + \text{diam}(H)$ — making it easy to compute routing distances in these structured networks.

Key Takeaways

1. The complement $\overline{G}$ swaps edges and non-edges. $G \cup \overline{G} = K_n$. Cliques in $G$ are independent sets in $\overline{G}$.
2. The union $G \cup H$ places two graphs side-by-side without any new edges. The result is always disconnected when $G$ and $H$ are vertex-disjoint.
3. The join $G \vee H$ is the union plus every possible cross-edge. Joining a single vertex to a cycle produces the wheel graph; joining two independent sets produces the complete bipartite graph.
4. The line graph $L(G)$ turns edges into vertices: two new vertices are adjacent iff their original edges shared an endpoint. It translates edge-colouring problems into vertex-colouring problems.
5. The Cartesian product $G \,\square\, H$ builds a grid-like graph: vertices are pairs $(g,h)$ and adjacency requires differing in exactly one coordinate along an existing edge. $P_m \,\square\, P_n$ is the $m \times n$ grid; repeated products of $K_2$ give the hypercube $Q_n$.
6. $Q_n$ is $n$-regular with $2^n$ vertices and $n \cdot 2^{n-1}$ edges. Its vertices are binary strings; adjacency = Hamming distance 1. It is the backbone of parallel computing and coding theory.

Explore Further

Use the GraphArena Playground to experiment:

• Build any 5-vertex graph and manually construct its complement. Overlay them — do you get $K_5$?
• Build $K_1$ and $C_4$. Use the join mentally: how many edges does $K_1 \vee C_4$ have? Draw it — is it $W_4$?
• Construct a small graph with 4 edges and draw its line graph $L(G)$ step-by-step using the midpoint rule.
• Build $P_3 \,\square\, P_3$ (a $3 \times 3$ grid). Count vertices and edges — verify the formula.
• Extend to $Q_2$: start with two copies of $K_2$, connect matching endpoints — do you get a square? Then repeat to build $Q_3$.

Graph operations are the grammar of graph theory — they let you express complex structured graphs concisely and reveal deep relationships between seemingly different graphs.