Skip to content
Tutorials Center
My learning

Topics

Lesson 9 of 36 ยท Graphs and Representations

Subgraphs and Isomorphism

Understand subgraphs, induced subgraphs, complements and graph isomorphism: decide when two drawings are the same graph, with invariants, brute force search and networkx checks.

Two natural questions come up again and again. First: which smaller graphs live inside a bigger one? That is the idea of a subgraph. Second: when are two graphs really the same? That is the idea of isomorphism. This lesson answers both and shows why the second question is much harder than it looks.

Subgraphs

A graph H is a subgraph of G if every vertex of H is a vertex of G and every edge of H is an edge of G. You obtain one by deleting some vertices and edges.

Two special kinds matter:

  • A spanning subgraph keeps all vertices and drops only edges. A spanning tree is the classic example (trees and forests).
  • An induced subgraph G[S] keeps a chosen set S of vertices and every edge of G between them. You choose only the vertices; the edges follow.
graph LR
  1 --- 2
  2 --- 3
  3 --- 4
  4 --- 1
  1 --- 3

Choose S = {1, 2, 3}: the induced subgraph is the triangle 1-2-3, including the diagonal edge 1-3. The subgraph with edges 1-2 and 2-3 only is a subgraph but not induced.

Python Induced subgraphs and deleting

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

A clique is a set of vertices whose induced subgraph is complete. An independent set is a set whose induced subgraph has no edges at all.

The complement

The complement แธ  of a simple graph G has the same vertices, and two vertices are adjacent in แธ  exactly when they are not adjacent in G. Cliques of G are independent sets of แธ  and vice versa. The edge counts satisfy m(G) + m(แธ ) = n(n-1)/2.

Python Complement of a graph

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Look closely at that output: the complement of the 5-cycle is another 5-cycle (0-2-4-1-3-0). A graph isomorphic to its own complement is called self-complementary.

Isomorphism

Two graphs G and H are isomorphic if there is a one-to-one relabeling of the vertices that turns the edges of G exactly into the edges of H. Formally, a bijection f: V(G) โ†’ V(H) such that {u, v} is an edge of G iff {f(u), f(v)} is an edge of H. Isomorphic graphs are the same graph drawn or named differently.

Invariants: quick ways to say "different"

If two graphs are isomorphic, they must agree on every structural property. These invariants let you rule out isomorphism cheaply:

  • the number of vertices and edges,
  • the degree sequence,
  • the number of triangles, connectivity, bipartiteness, and so on.

Different invariants prove that two graphs are not isomorphic. Equal invariants, however, prove nothing: you still need an actual bijection.

Brute force

Try every relabeling. For n vertices there are n! of them, which is fine for tiny graphs and hopeless for large ones.

Python Brute-force isomorphism test

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The first answer gives a concrete mapping. The second graph has the right number of edges but a different degree sequence, so the cheap invariant check settles it.

Equal degree sequences, still different

Python Same degrees, different graphs

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Both graphs have six vertices, six edges and degrees (2,2,2,2,2,2), but one is connected and the other is not. Connectivity is another invariant that separates them.

Why isomorphism matters

Chemists compare molecules (are these two structural diagrams the same compound?), software tools detect duplicated structures, and cryptographers study the problem for its unknown complexity: no polynomial-time algorithm is known for general graph isomorphism, yet it is not known to be NP-complete either. Practical programs such as nauty and networkx use clever refinement of invariants and handle large graphs well in practice.

Automorphisms

An isomorphism from a graph to itself is an automorphism. The triangle has 6 automorphisms (all permutations of its 3 vertices). The more symmetric a graph, the more automorphisms it has; a graph with only the identity automorphism is called asymmetric.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What distinguishes an induced subgraph on a vertex set S from a general subgraph on S?

    In an induced subgraph you choose only the vertices; all edges of G among them are kept.
  2. 2. A graph G has 10 vertices and 18 edges. How many edges does its complement have?

    K10 has 45 edges, so the complement has 45 - 18 = 27.
  3. 3. Two graphs have different degree sequences. What can you conclude?

    Isomorphic graphs have identical degree sequences, so a difference proves they are not isomorphic.
  4. 4. Two graphs have the same degree sequence. What can you conclude?

    Two triangles and a hexagon both have six vertices of degree 2, but they are not isomorphic.

Summary

  • A subgraph keeps some of the vertices and edges; an induced subgraph keeps all edges among chosen vertices.
  • The complement flips adjacency: m + mฬ„ = n(n-1)/2.
  • Isomorphic graphs are the same up to relabeling vertices.
  • Invariants (edges, degrees, connectivity) can prove two graphs differ but never that they match.
  • General graph isomorphism has no known polynomial algorithm; brute force is n!.

Next: Walks, Paths and Cycles