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.

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),

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

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.