graph theorygraph-isomorphism
I know that the 3 graphs have the same number of vertices and edges which is one of the condition for isomorphism . And I also know that having the same number of vertices and edges does not mean that they already isomorphic to each other. My question is, if there's pair in the graph that is isomorphic to each other, what is it and how I can prove it by mapping the vertices?
Once you know, as pointed out in this answer, that $$f(A)=7,\: f(B)=4,\: f(C)=3,\: f(D)=6,\: f(E)=5,\: f(F)=2,\: f(G)=1$$ isomorphism, you can create an animation illustrating how to morph one graph into the other. Let's say that ${vc}_1$ is a list of vertex coordinates for one and ${vc}_2$ is the corresponding list of vertex coordinates for the other. (It's important that the order of the vertex coordinates be dictated by the isomorphism.) We can then morph from one graph to the other using a function like
$$p(t) = t \, {vc}_2 + (1-t) {vc}_1.$$
Here's the result:
Since several folks asked for code generating the animation in the comments, you can find it here:
A more formal justification would argue that the multiset of vertex degrees is a graph invariant; that is, a property of the graph that is the same for every graph isomorphic to it. Since these two graphs have different multisets of vertex degrees, they cannot be isomorphic.
We can see that the multiset of vertex degrees is a graph invariant because an isomorphism always maps a vertex of degree d to another vertex of degree d. That can be directly argued from the definition of isomorphism.
Note that degree sequences of graphs are not an invariant, as the degree sequence may be permuted by an isomorphism.
Best Answer
After you have verified that each graph contains a unique triangle, label each vertex of each graph with its distance from the triangle. That is, start by labeling the vertices of the triangle with $0$, then label their unlabeled neighbors with $1$, then label the unlabeled neighbors of those vertices with $2$, and so on.
When I did this I found that each graph has three vertices labeled $0$ (of course), and three vertices labeled $1$; but graph A has four vertices labeled $2$ and two vertices labelled $3$, while graph B has five vertices labeled $2$ and one vertex labeled $3$, and graph C has three vertices labeled $2$ and three vertices labeled $3$.
This means that no two of the three graphs are isomorphic.