Degree sequence equal iff graph isomorphism?

✍️ → Written on 2019-11-19 in 546 words. Part of math discrete-mathematics

Motivation

Plagiarism in student submissions is frequently a problem. Some trivial algorithm to detect “variable renaming” in student submissions would be characterizing variables by the number of references within a program. Consider the following rust program:

let a = 42;
let b = 32 + a;
let c = 2 * (a - b) + a.pow(2);

This program should be determined to be equivalent to the following program:

let c = 42;
let b = 32 + c;
let a = 2 * (c - b) + c.pow(2);

Apparently, the first variable is used 4 times in total. The second variable is used twice and the third variable is used once. In this particular problem, the counts are distinctive. But does this work fundamentally for larger programs?

The problem

  • An [undirected] graph is a tuple of vertices (V) and edges (E)

  • Vertices are any distinctive elements and edges are sets of two different vertices

  • e.g. ({v₀, v₁, v₂}, {{v₀, v₁}, {v₁, v₂}}) is an undirected graph

  • The degree of a vertex is defined as the number of edges containing the given vertex

  • e.g. In ({v₀, v₁, v₂}, {{v₀, v₁}, {v₁, v₂}}), deg(v₁) = 2 but deg(v₀) = 1.

  • A degree sequence is the monotonically decreasing sequence of degrees of vertices of a graph.

  • e.g. ({v₀, v₁, v₂}, {{v₀, v₁}, {v₁, v₂}}) has degree sequence (2, 1, 1)

  • An isomorphism between graph G₀ and G₁ is given if we can rename the vertices of G₀ such that G₁ is given

  • e.g. ({v₀, v₁, v₂}, {{v₀, v₁}, {v₁, v₂}}) is isomorphic to ({v₀, v₁, v₂}, {{v₀, v₂}, {v₁, v₂}})

  • e.g. ({v₀, v₁, v₂}, {{v₀, v₁}}) is not isomorphic to ({v₀, v₁, v₂}, {{v₀, v₂}, {v₁, v₂}})

Claim

Two graphs are isomorphic if and only if their degree sequences are equal.

Result

Graph at the top with sequence A-B-C-D-E as well as B-F-G-H. And one graph at the bottom with sequence A-B-C-D-E-F-G as well as H-B

This counterexample shows that two graphs can have the same degree sequence (3, 2, 2, 2, 2, 1, 1, 1), but are isomorphic (one property violating isomorphism is that the number of neighbors, of the vertex with degree 3, with degree 1 is 1 and 2 respectively → a difference yields non-isomorphism). Trivially, this example can be found on Wikipedia.

On the other hand: If a graph is isomorphic, we can apply the relabelling to retrieve the same graph. Obviously the degree sequence of two equivalent graphs are the same.

Thus: isomorphism ⇒ equal degree sequences. equal degree sequences ⤃ isomorphism.

With respect to our motivational example, this means two different programs might be recognized as the same w.r.t. “variable renaming”.