Skip to content
Tutorials Center
My learning

Topics

Lesson 50 of 68 ยท Graph Theory

Graph Isomorphism and Drawing Graphs

Decide when two graphs are the same, use invariants to tell them apart, and draw graphs with a hand-written spring layout in matplotlib.

Two drawings can look completely different and still show the same graph. Rename the vertices, move them around, bend the edges, and nothing about the connections has changed. Graph isomorphism is the precise way to say "these two graphs are the same up to renaming": there is a one-to-one matching between their vertices that turns edges into edges and non-edges into non-edges.

This lesson has two halves. First we decide isomorphism: a brute-force check, plus cheap invariants (degree sequence, triangle count and more) that quickly prove two graphs are different. Then we turn to drawing: how a picture is just a choice of coordinates, how a spring layout finds good ones by simulating forces, and how to read what a graph picture does and does not tell you. Everything uses plain Python plus matplotlib, and builds on graph terms and representations.

Same graph, different pictures

Isomorphic A renaming of vertices maps edges to edges exactly.
Invariants Properties every renamed copy shares.
Drawings Coordinates are a choice, not part of the graph.
1 / 2

What isomorphism means

Graphs G and H are isomorphic (written G โ‰… H) if there is a bijection f from the vertices of G to the vertices of H such that u and v are adjacent in G exactly when f(u) and f(v) are adjacent in H. The bijection is called an isomorphism.

A few consequences follow right away. Isomorphic graphs have the same number of vertices and edges. A vertex of degree 3 must map to a vertex of degree 3. Cycles map to cycles of the same length. Any property that depends only on the pattern of connections, and not on the vertex names, is shared by both graphs. Such a property is called a graph invariant.

The brute-force test is direct: try every bijection and see whether one preserves adjacency. With n vertices there are n! bijections, which is fine for ten vertices and hopeless for fifty. Even so, brute force is a good reference implementation for small cases.

Python Brute-force isomorphism check

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.

Notice that the answer for the first pair is not unique: a 5-cycle can be matched to another 5-cycle in ten different ways (five rotations, each possibly reflected). The function returns the first one it finds. Two matchings of a graph onto itself are called automorphisms, and the number of automorphisms measures how symmetric a graph is. We return to symmetry in groups.

Invariants: proving graphs are different

To show two graphs are not isomorphic you do not need to try any bijection. It is enough to find one invariant on which they disagree. Useful cheap invariants are:

  • the number of vertices and the number of edges,
  • the degree sequence, the sorted list of degrees (also the handshake lemma: degrees sum to twice the edges),
  • the number of connected components,
  • the number of triangles, or more generally the number of cycles of each length,
  • whether the graph is bipartite, and the length of its shortest cycle (the girth).

Invariants only work in one direction. If an invariant differs, the graphs are definitely not isomorphic. If every invariant you computed agrees, the graphs may still be different. The classic example: two disjoint triangles versus one 6-cycle. Both have 6 vertices, 6 edges and the degree sequence [2, 2, 2, 2, 2, 2]. They differ in connectivity (two components versus one), so a single extra invariant separates them.

Python Invariants as a quick filter

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 last two lines show the idea well: the prism (two triangles joined by three rungs) and K_{3,3} agree on vertices, edges and every degree, yet the prism contains triangles and K_{3,3} is bipartite so it has none. One invariant is enough to prove they are different graphs.

For serious work, a smarter search than raw n! is used: match vertices only when their degrees agree, extend the matching one vertex at a time, and abandon a partial matching as soon as an edge is violated. No algorithm is known that decides isomorphism in polynomial time in every case, yet the problem is also not known to be NP-complete, which makes it a famous in-between case. Practical libraries solve almost all real inputs quickly.

Drawings are not graphs

A drawing of a graph assigns each vertex a point in the plane and draws each edge as a curve (here, a straight segment). The graph itself contains no coordinates at all. Many different drawings show the same graph, and a bad drawing can hide its structure completely.

Good drawings tend to follow a few rules of thumb: keep adjacent vertices close, keep non-adjacent vertices apart, avoid edge crossings when you can, and show symmetry when the graph has it. Planar graphs (see coloring and planarity) can be drawn with no crossings at all, but you must pick coordinates cleverly.

The simplest layout is the circular layout: put the vertices evenly on a circle. It is easy and always readable, but it often produces many crossings. A better general-purpose method treats the graph as a physical system.

A spring layout from scratch

The spring layout (also called the Fruchterman-Reingold idea) imagines two forces:

  1. every pair of vertices repels each other, like charged particles, with strength falling off as kยฒ / distance,
  2. every edge acts like a spring that pulls its two ends together, with strength distanceยฒ / k.

Start with positions chosen by a fixed random seed, then repeat: compute the net force on each vertex, move each vertex a small step in that direction, and shrink the step size over time (a "cooling" schedule). After a few hundred iterations the picture settles into a balanced shape where connected vertices sit near each other and the rest spread out.

Python Writing a spring layout and drawing with matplotlib

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 panels show the same 3 by 3 grid graph. The circular drawing squeezes its edges across the middle and crosses many of them; the spring drawing recovers the familiar square grid with no crossings at all, because springs pull neighbors together while repulsion spreads everything out. The two printed counts confirm what you see. Because the starting positions come from a seeded generator, the picture is the same every time you run it. Change seed and you get a rotated or mirrored version, which is exactly the point: the layout is not the graph.

Spring layouts do have weaknesses. They cost about O(nยฒ) per iteration because of the all-pairs repulsion, they can get stuck in a poor local arrangement, and for large graphs they produce "hairballs". Real libraries use faster approximations, but the idea is the one you just wrote.

Reading graph pictures

When you look at a graph drawing, be careful about what the picture actually says.

  • Position carries no meaning. Two vertices being close in a spring layout suggests they are well connected, but distance, angle and which vertex is "in the middle" are artifacts of the algorithm.
  • Crossings are not vertices. Where two edges cross in a drawing, nothing exists unless a dot is drawn. Planarity is about whether some drawing has no crossings.
  • Look for structure. Dense clumps suggest communities, a single vertex linking two clumps is a cut vertex (see paths and connectivity), a long thin chain suggests a path, and a hub with many spokes suggests a star.
  • Compare by invariants, not by eye. Two drawings that look different may be isomorphic, and two that look alike may differ in one edge. Count degrees and edges before you trust your eyes.

A good habit when you meet an unfamiliar drawing is to translate it into an edge list and compute its invariants. That turns a picture into data you can reason about.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Two graphs have the same number of vertices, the same number of edges and the same degree sequence. What can you conclude?

    Invariants can only prove graphs are different. Two triangles and a 6-cycle share all three values yet are not isomorphic.
  2. 2. Which finding proves two graphs are NOT isomorphic?

    A triangle count is an invariant, so a difference proves non-isomorphism. Looks, names and layouts are not part of the graph.
  3. 3. How many bijections does the brute-force check try, in the worst case, for graphs on n vertices?

    Each bijection is a permutation of the n vertices, and there are n! of them.
  4. 4. In a spring layout, what do the two forces do?

    Repulsion between all pairs spreads the picture out, and edge springs keep neighbors close. The balance gives a readable layout.

Summary

  • Graphs are isomorphic when a vertex bijection preserves adjacency and non-adjacency; renaming or redrawing never changes the graph.
  • Brute force tries n! bijections; it is a fine reference for small graphs but does not scale.
  • Invariants (vertex and edge counts, degree sequence, components, triangles, girth, bipartiteness) prove non-isomorphism when they differ, but agreement proves nothing.
  • A drawing is just coordinates; the same graph has many pictures, and the circular layout is simple but crossing-heavy.
  • A spring layout simulates repulsion between all vertices and spring attraction along edges, cooling the step size over time.
  • Read pictures cautiously: positions and crossings are artifacts, so compare graphs by their data.

Next: Boolean Algebra and Logic Circuits, where logic turns into hardware.