# Chapter 12. Graph Operations

# Chapter 12. Graph Operations

Graph operations build new graphs from old graphs. Some operations remove vertices or edges. Some combine two graphs. Some transform the incidence structure while preserving part of the original graph.

These operations are useful for two reasons. First, they give concise ways to construct examples. Second, they support proofs by reduction: one studies how a property changes when a graph is modified.

Common graph operations include union, intersection, complement, deletion, contraction, subdivision, join, and graph products. Standard references distinguish unary operations, which act on one graph, from binary operations, which combine two graphs.

## 12.1 Unary and Binary Operations

A **unary graph operation** takes one graph as input and produces one graph as output.

Examples include:

| Operation | Input | Output |
|---|---|---|
| Vertex deletion | \(G\) and a vertex \(v\) | \(G-v\) |
| Edge deletion | \(G\) and an edge \(e\) | \(G-e\) |
| Edge contraction | \(G\) and an edge \(e\) | \(G/e\) |
| Complement | \(G\) | \(\overline{G}\) |
| Subdivision | \(G\) and an edge \(e\) | A graph with \(e\) replaced by a path |

A **binary graph operation** takes two graphs and produces one graph.

Examples include:

| Operation | Inputs | Output |
|---|---|---|
| Union | \(G,H\) | \(G \cup H\) |
| Intersection | \(G,H\) | \(G \cap H\) |
| Join | \(G,H\) | \(G+H\) |
| Cartesian product | \(G,H\) | \(G \square H\) |
| Disjoint union | \(G,H\) | \(G \dot{\cup} H\) |

Unary operations modify one graph. Binary operations combine two graphs.

## 12.2 Union of Graphs

Let

$$
G=(V_G,E_G)
$$

and

$$
H=(V_H,E_H)
$$

be graphs. Their **union** is the graph

$$
G \cup H
$$

with vertex set

$$
V(G \cup H)=V_G \cup V_H
$$

and edge set

$$
E(G \cup H)=E_G \cup E_H.
$$

The union contains all vertices and all edges appearing in either graph. If a vertex or edge appears in both graphs, it appears only once in the union.

For example, if

$$
E_G=\{\{a,b\},\{b,c\}\}
$$

and

$$
E_H=\{\{c,d\},\{a,b\}\},
$$

then

$$
E(G\cup H)=\{\{a,b\},\{b,c\},\{c,d\}\}.
$$

The shared edge \(\{a,b\}\) is not duplicated. This set-theoretic definition of graph union is the usual one.

## 12.3 Intersection of Graphs

The **intersection** of two graphs \(G\) and \(H\) is the graph

$$
G \cap H
$$

with vertex set

$$
V(G \cap H)=V_G \cap V_H
$$

and edge set

$$
E(G \cap H)=E_G \cap E_H.
$$

The intersection keeps only the vertices and edges common to both graphs.

For example, if

$$
E_G=\{\{a,b\},\{b,c\},\{c,d\}\}
$$

and

$$
E_H=\{\{a,b\},\{c,d\},\{d,e\}\},
$$

then

$$
E(G\cap H)=\{\{a,b\},\{c,d\}\}.
$$

Graph intersection is useful when two graphs describe different relations on overlapping objects, and one wants the part common to both.

## 12.4 Disjoint Union

The **disjoint union** of graphs combines them without identifying vertices.

Even if \(G\) and \(H\) use the same vertex labels, the disjoint union treats the two copies as separate unless they have first been explicitly identified.

It is often written as

$$
G \dot{\cup} H.
$$

Formally, one may replace the vertices of \(G\) by pairs

$$
(v,1)
$$

and the vertices of \(H\) by pairs

$$
(w,2).
$$

Then the vertex sets are disjoint by construction.

The disjoint union has no edges between the copy of \(G\) and the copy of \(H\). Therefore, if both graphs are nonempty, the disjoint union is disconnected.

Disjoint union is useful for building graphs component by component.

## 12.5 Ring Sum and Symmetric Difference

The **ring sum** of two graphs is formed by taking the symmetric difference of their edge sets.

It is often written as

$$
G \oplus H.
$$

The edge set is

$$
E(G\oplus H)=E_G \triangle E_H,
$$

where

$$
E_G \triangle E_H =
(E_G\setminus E_H)\cup(E_H\setminus E_G).
$$

Thus an edge appears in \(G\oplus H\) exactly when it appears in one graph but not both.

Depending on convention, the vertex set may be taken as

$$
V_G \cup V_H
$$

or restricted to vertices incident with edges of the symmetric difference. The convention should be stated before use.

For example, if

$$
E_G=\{\{a,b\},\{b,c\}\}
$$

and

$$
E_H=\{\{b,c\},\{c,d\}\},
$$

then

$$
E(G\oplus H)=\{\{a,b\},\{c,d\}\}.
$$

The common edge \(\{b,c\}\) disappears.

## 12.6 Complement

Let \(G\) be a simple graph with vertex set \(V\). The **complement** of \(G\), written

$$
\overline{G},
$$

is the simple graph with the same vertex set, where two distinct vertices are adjacent in \(\overline{G}\) exactly when they are not adjacent in \(G\).

Thus

$$
V(\overline{G})=V(G).
$$

For distinct vertices \(u,v\),

$$
\{u,v\}\in E(\overline{G})
$$

if and only if

$$
\{u,v\}\notin E(G).
$$

If \(G\) has \(n\) vertices and \(m\) edges, then

$$
\overline{G}
$$

has

$$
\binom{n}{2}-m
$$

edges.

The complement turns non-adjacency into adjacency. It is useful in coloring, clique theory, independent sets, and extremal graph theory.

## 12.7 Vertex Deletion

Let \(G\) be a graph and let \(v\in V(G)\). The graph

$$
G-v
$$

is obtained by deleting \(v\) and all edges incident with \(v\).

Thus

$$
V(G-v)=V(G)\setminus\{v\}.
$$

The edge set consists of all edges of \(G\) whose endpoints are not \(v\).

More generally, if \(S\subseteq V(G)\), then

$$
G-S
$$

is obtained by deleting every vertex in \(S\) and all incident edges.

Vertex deletion is used in cut vertices, induced subgraphs, graph minors, recursive algorithms, and deletion proofs.

## 12.8 Edge Deletion

Let \(e\in E(G)\). The graph

$$
G-e
$$

is obtained by deleting the edge \(e\) while keeping all vertices.

Thus

$$
V(G-e)=V(G)
$$

and

$$
E(G-e)=E(G)\setminus\{e\}.
$$

More generally, if \(F\subseteq E(G)\), then

$$
G-F
$$

deletes all edges in \(F\).

Edge deletion produces a spanning subgraph. It is used in forests, spanning trees, bridges, cuts, and deletion-contraction recurrences. Lecture notes commonly define \(G-e\) as the edge-deleted subgraph of \(G\).

## 12.9 Edge Addition

If \(u\) and \(v\) are distinct nonadjacent vertices of a simple graph \(G\), then

$$
G+\{u,v\}
$$

is the graph obtained by adding the edge \(\{u,v\}\).

The vertex set remains unchanged:

$$
V(G+\{u,v\})=V(G).
$$

The edge set becomes

$$
E(G+\{u,v\})=E(G)\cup\{\{u,v\}\}.
$$

Adding an edge can reduce the number of connected components by at most one. If \(u\) and \(v\) are already in the same component, the number of components does not change. If they are in different components, those two components merge.

In a tree, adding any new edge creates exactly one cycle.

## 12.10 Edge Contraction

Let

$$
e=\{u,v\}
$$

be an edge of an undirected graph \(G\). The **contraction** of \(e\), written

$$
G/e,
$$

is obtained by identifying \(u\) and \(v\) into a single new vertex and keeping the remaining adjacencies.

Intuitively, the edge \(e\) is shrunk to a point.

If \(u\) and \(v\) are merged into a new vertex \(x\), then every edge incident with \(u\) or \(v\) becomes incident with \(x\). The edge \(e\) itself disappears.

Contraction may create loops or multiple edges. In simple graph theory, loops are usually deleted and parallel edges may be merged after contraction.

Edge contraction is fundamental in graph minors, planar graph theory, spanning tree recurrences, and network simplification.

## 12.11 Subdivision

A **subdivision** replaces an edge by a path.

If

$$
e=\{u,v\}
$$

is an edge of \(G\), subdividing \(e\) means deleting \(e\), adding a new vertex \(x\), and adding two edges

$$
\{u,x\}
$$

and

$$
\{x,v\}.
$$

Thus the edge

$$
u-v
$$

is replaced by

$$
u-x-v.
$$

Subdivision preserves many topological features of a graph while changing degrees and path lengths. It is important in planar graph theory, homeomorphism of graphs, graph drawing, and topological minors.

Repeated subdivision replaces an edge by a longer path.

## 12.12 Join of Graphs

Let \(G\) and \(H\) be vertex-disjoint graphs. The **join** of \(G\) and \(H\), written

$$
G+H
$$

or sometimes

$$
G \vee H,
$$

is obtained from their disjoint union by adding every possible edge between a vertex of \(G\) and a vertex of \(H\).

Thus

$$
V(G+H)=V(G)\cup V(H)
$$

and

$$
E(G+H) =
E(G)\cup E(H)
\cup
\{\{u,v\}:u\in V(G),\ v\in V(H)\}.
$$

The join makes every vertex of \(G\) adjacent to every vertex of \(H\). This is the standard construction used in graph operations.

For example,

$$
K_m + K_n = K_{m+n}.
$$

Joining two complete graphs gives a larger complete graph.

## 12.13 Cartesian Product

The **Cartesian product** of graphs \(G\) and \(H\) is written

$$
G \square H.
$$

Its vertex set is

$$
V(G \square H)=V(G)\times V(H).
$$

Two vertices

$$
(g,h)
$$

and

$$
(g',h')
$$

are adjacent if either:

$$
g=g'
$$

and

$$
\{h,h'\}\in E(H),
$$

or

$$
h=h'
$$

and

$$
\{g,g'\}\in E(G).
$$

Thus movement in the product changes one coordinate at a time. This is the standard definition of the Cartesian product of graphs.

For example, the grid graph can be written as

$$
P_m \square P_n.
$$

It has \(m n\) vertices arranged like an \(m\)-by-\(n\) rectangular grid.

## 12.14 Other Graph Products

Several other graph products are used in graph theory.

The **tensor product**, also called the direct product, has vertex set

$$
V(G)\times V(H),
$$

where two vertices are adjacent when both coordinates move along edges.

The **strong product** combines the Cartesian and tensor product rules. Two product vertices are adjacent if one coordinate moves, the other coordinate moves, or both move simultaneously. The strong product of path graphs models king moves on a grid.

The **lexicographic product** replaces each vertex of one graph by a copy of another graph.

Graph products are used in algebraic graph theory, network construction, coding theory, distributed computing, and metric graph theory.

## 12.15 Line Graph

The **line graph** of a graph \(G\), written

$$
L(G),
$$

is the graph whose vertices are the edges of \(G\).

Two vertices of \(L(G)\) are adjacent when the corresponding edges of \(G\) share an endpoint.

For example, if \(G\) is the path

$$
a-b-c,
$$

then \(G\) has two edges:

$$
\{a,b\}
$$

and

$$
\{b,c\}.
$$

These two edges share the endpoint \(b\), so \(L(G)\) is a graph with two adjacent vertices.

Line graphs convert edge questions into vertex questions. Matchings in \(G\), for example, correspond to independent sets in \(L(G)\).

## 12.16 Graph Powers

The **\(k\)-th power** of a graph \(G\), written

$$
G^k,
$$

has the same vertex set as \(G\). Two distinct vertices are adjacent in \(G^k\) when their distance in \(G\) is at most \(k\).

Thus

$$
\{u,v\}\in E(G^k)
$$

if and only if

$$
1\leq d_G(u,v)\leq k.
$$

The first power is the graph itself:

$$
G^1=G.
$$

The square \(G^2\) adds edges between vertices at distance \(2\). Graph powers are useful in network reachability, coloring, bandwidth problems, and distance-based graph theory.

## 12.17 Operation Effects

Graph operations change graph parameters in predictable ways.

| Operation | Vertices | Edges | Typical effect |
|---|---:|---:|---|
| Vertex deletion | Decreases | Decreases | May disconnect graph |
| Edge deletion | Same | Decreases | May create more components |
| Edge addition | Same | Increases | May create cycles or merge components |
| Contraction | Decreases | Usually decreases | Shortens paths, may create parallel edges |
| Complement | Same | Replaces edges by non-edges | Exchanges cliques and independent sets |
| Join | Adds vertices | Adds all cross edges | Strongly increases connectivity |
| Cartesian product | Multiplies vertex counts | Combines coordinate moves | Builds grid-like graphs |

These effects help in proofs. For example, deleting edges can produce a spanning tree. Adding edges to a tree creates cycles. Taking complements converts clique questions into independent set questions.

## 12.18 Example

Let

$$
G
$$

have vertex set

$$
\{a,b,c\}
$$

and edge set

$$
\{\{a,b\},\{b,c\}\}.
$$

Thus \(G=P_3\).

The complement \(\overline{G}\) has the same vertex set and edge set

$$
\{\{a,c\}\}.
$$

Deleting the edge \(\{a,b\}\) gives

$$
G-\{a,b\},
$$

with edge set

$$
\{\{b,c\}\}.
$$

Contracting the edge \(\{a,b\}\) merges \(a\) and \(b\). The resulting graph has two vertices and one edge between the merged vertex and \(c\).

Subdividing the edge \(\{b,c\}\) adds a new vertex \(x\) and replaces

$$
b-c
$$

by

$$
b-x-c.
$$

These operations all begin with the same graph but produce different structural changes.

## 12.19 Summary

Graph operations construct new graphs from existing graphs. Unary operations modify one graph through deletion, addition, contraction, subdivision, complementation, line graph construction, or graph powers. Binary operations combine graphs through union, intersection, disjoint union, join, and graph products.

These operations are not merely notation. They are tools for building examples, proving theorems, designing algorithms, and comparing graph structures. Many later topics, including trees, minors, planar graphs, colorings, products, and spectral graph theory, depend on understanding how graph operations change vertices, edges, paths, cycles, and connectivity.