No, you cannot map an each edge in $G_1$ to an arbitrary one in $G_2$. For example the 1-4 edge in your $G_1$ connects a degree-3 vertex with a degree-2 vertex, and cannot map isomorphically to the 1-4 edge in $G_2$ which goes bewteen the two degree-3 vertices.
Rather than having two isomorphic graphs, it seems to be easier to think in terms of how many automorphisms from a graph to itself there are. I don't know any easy systematic way to count that (in fact the references I can google up look like it is just as hard as deciding graph isomorphisms, which is suspected to be impossible in polynomial time).
In this particular case, it is fairly easy to see there are exactly 4 isomorphisms -- you can permute the two degree-2 nodes freely, and for each choice here you get a free choice of permutation for the two nodes of degree 3. But you can't send any node with one arity to one with another.
In general, it's a hard problem
There's no known efficient algorithm that is guaranteed to tell you whether two graphs are isomorphic. Of course, we could try all possible permutations of the vertices, but this will take a very long time. We know heuristics: good things to try which will work in many cases, but will sometimes give us an inconclusive answer.
But we can solve it by hand for small examples
In practice, when the number of vertices is not too large, we can often check for isomorphism without too much work. We do this by picking out distinguishing features of the vertices in each graph. Then we have fewer bijections between the vertex sets to check to see if the graphs are isomorphic.
One of the simplest distinguishing features of a vertex is its degree: the number of edges out of that vertex. For the example in the question, we notice that:
- Vertices $\{A, B, E, F, H, I\}$ of the first graph have degree $3$, and vertices $\{C,D,G\}$ have degree $4$.
- Vertices $\{4, 5, 6, 7, 8, 9\}$ of the second graph have degree $3$, and vertices $\{1,2,3\}$ have degree $4$.
So we have reduced our search space significantly from $9! = 362,880$ to $6! \cdot 3! = 4,320$ graph isomorphisms: that's the number of bijections between the vertex sets that send $\{A,B,E,F,H,I\}$ to $\{4,5,6,7,8,9\}$ and $\{C,D,G\}$ to $\{1,2,3\}$. (And if the numbers of vertices of each degree didn't match up, we'd know very quickly that there's no graph isomorphism.)
We can further distinguish between the vertices of each degree. For instance, in the first graph, $\{A,E,I\}$ are vertices of degree $3$ that are adjacent to vertices of degree $4$; $\{B,F,H\}$, on the other hand, are vertices of degree $3$ whose neighbors all have degree $3$. This narrows the search space even more.
If we start filling in a partial graph isomorphism, pieces fall into place as we go. For example, we could try seeing if there's a graph isomorphism that maps $C$ to $1$. Then $A$ (a neighbor of $C$ which has degree $3$) must be mapped to $4$ or $6$ (neighbors of $1$ which have degree $3$). If $A$ is mapped to $4$, then $D$ (a neighbor of $A$ and $C$) must map to $3$ (a neighbor of $1$ and $4$), and pretty soon the entire isomorphism is there.
To make this work, we will need to do some casework, and might need to backtrack, but usually you should not expect to have many branches to try. Highly symmetric graphs are harder to tackle this way, and in fact they are the places where computer algorithms stumble, too.
Another example of looking at degrees
Here is another example of graphs we might analyze by looking at degrees of vertices.
If we write down the degrees of all vertices in each graph, in ascending order, we get:
- $2, 2, 2, 3, 3, 4, 5, 5$ for the graph on the left;
- $2, 2, 3, 3, 3, 4, 4, 5$ for the two other graphs.
This tells us that the first graph is not isomorphic to the other two, because the degree sequences don't match up.
Importantly, it does not tell us that the two other graphs are isomorphic, even though they have the same degree sequence. In fact, they are not isomorphic either: in the middle graph, the unique vertex of degree $5$ is adjacent to a vertex of degree $2$, and in the graph on the right, the unique vertex of degree $5$ is only adjacent to vertices of degree $3$ or $4$.
Graph invariants
A more general approach to graph isomorphism is to look for graph invariants: properties of one graph that may or may not be true for another. (The degree sequence of a graph is one graph invariant, but there are many others.) This is usually a quick way to prove that two graphs are not isomorphic, but will not tell us much if they are.
For example:
- Is the number of vertices and edges in one graph the same as in the other?
- If one graph is planar, is the other graph also planar?
- If one graph is bipartite, is the other graph also bipartite?
- If one graph contains two cycles of length $3$, does the other graph also contain two cycles of length $3$?
More elaborate invariants exist. For example, we can compute the Tutte polynomial of both graphs: if we get different values, then the graphs are not isomorphic. Unfortunately, if two graphs have the same Tutte polynomial, that does not guarantee that they are isomorphic.
Links
Best Answer
To add to the answer of user108903, to prove two graphs are not isomorphic, you need to find some graph property that one has but the other doesn't. Sometimes this is easy and sometimes this is not (sometimes it's as easy as showing their degree sequences are different). user108903's suggestion here is to see which ones are bipartite. In this case, that works to show Graph 3 is not isomorphic to 1 or 2. An equivalent way would be to find the chromatic numbers of the graphs. If you look at a graph theory textbook on this subject, there will probably be a few examples where they show different ways to prove two graphs are non-isomorphic. I know Graphs and Digraphs by Chartrand, et al, does.
Another way that would work here would be to look at the independence numbers of the graphs. I think that finding the largest induced cycle would also do the trick. I believe you can find one of length 5 in graph 3, whereas you can not find one of odd order in any bipartite graph, to go back to the hint of user108903.
To show that two graphs are actually isomorphic, you need to construct an isomorphism from one to the other. So, construct a map from graph 1 to 2 that preserves adjacency/non-adjacency. There is not some finite list of properties you can check to determine if two graphs are isomorphic, as far as I know.