Equivalence Graphs

Question

On the basis of this definition:

Two graphs are equivalent if they have the same set of edges (ex. (A,B),(A,C)) how would you determine equivalence for graphs that are not labelled:

ex.

Answer 1

This is not a good definition:

Two graphs are equivalent if they have the same set of edges (ex. (A,B),(A,C)).

It should be:

Two graphs are equal if they have the same vertex set and the same set of edges.

E.g. these two graphs are equal:

(although they are drawn differently) and no two of these three graphs are equal:

Equivalence (typically called isomorphism) should be:

Two graphs are equivalent if their vertices can be relabeled to make them equal.

E.g. these two graphs are equivalent:

(we replace the label $8$ by $4$ and the label $5$ by $3$).

These two graphs are also equivalent:

(in fact, they are the same two graphs in the previous example, but the second is drawn differently).

So, to answer the question how would you determine equivalence for graphs that are not labelled, we assign labels to the vertices of the graphs in such a way to make them equal. In general, it's a non-trivial problem to determine whether or not it is possible to do this.

Answer 2

What you are asking is how to solve the graph isomorphism problem:

http://en.wikipedia.org/wiki/Graph_isomorphism_problem

Which is a curious but difficult problem at the moment. Of course, it is easy to see that, for example, graphs $J$ and $L$ in your example are equivalent, as are $K$ and $M$. The harder question is whether $L$ and $M$ are equivalent. For that, label the graphs like so:

Now, you want to relabel $a,b,\dots, g$ into $1,2,\dots, 7$ so that if two letters are connected, then the corresponding numbers are as well and vice versa. You can immediatelly see that $a$ and $1$ are the only two vertices with only one edge, meaning you must map $a$ to $1$. Next, since $(a,b)$ is an edge in $L$, and the only edge in $M$ containing $1$ is $(1,2)$, you must also map $b$ to $2$.

Next, you can see that $b$ has $2$ neighbors, one with degree $3$ and one with degree $4$, and the same is true for $2$ in $M$. This means you must map $c$ (the degree $3$ neighbor of $b$ in $L$) to $3$ (the degree $3$ neighbor of $2$ in $M$) and $d$ to $4$.

Now, $c$ has three neighbors in $L$, $b,d$ and $f$, so $3$ needs the same number of neighbors in $M$, meaning you must map $f$ to $5$, and then $g$ to $6$, leaving you to map $e$ to $7$, constructing the following mapping: $$f(a)=1\\ f(b)=2\\ f(c) = 3\\ f(d) = 4\\ f(e) = 7\\ f(f) = 5\\ f(g) = 6$$

---

Notice that the following mapping was not really "chosen" by me, but rather it was the only relabling of the graph that could result in graph equivalence. If you prove that it indeed does (and it does), you have proven equivalence.

Answer 3

You can eithre show that some specific feature is present in one graph and not in the other; or explicitly construct an isomorphism (i.e. a bijection between the sets of verticves that is compatible with the edges). There is no general simple formula.

Fortunately, the four graphs depicted here have a few specific features (exactly one vertex of degree $1$, exactly one vertex of degree $4$) that allow to readily construct the desired isomorphisms.