Yes, there are. I'll describe two such graphs.
First, arrange the six vertices in a 2 by 3 grid. Then connect vertices so as to form the number $8$ as seen on sports scoreboards or some digital clocks. This is what a commenter refers to as a theta graph.
For the second example, call the vertices of degree $3$ $A$ and $B$ and the other four $x,y,z,w$. Set $A$ adjacent to $x,y,z$, $B$ adjacent to $x,y,w$, and $z$ adjacent to $w$.
In the first example, the degree $3$ vertices are adjacent but in the second they are not, so the two graphs are non-isomorphic.
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
Consider an arbitrary isomorphism, $G'$, of $G$, and its corresponding bijection, $f$. We must preserve the adjacency and non adjacency of $G$.
Let us start (without loss of generalization) with $a$, which we will map to an arbitrary vertex of degree 2 in $G'$. We have 4 choices possible. Notice that no matter which vertex you pick, its neighbors will be $v$, a vertex of degree 2, and $w$, a vertex of degree 3. Since we must preserve the adjacency and non adjacency of $G$, it follows that the vertex of degree 3 must be labelled $b$, and the vertex of degree 2 must be labelled $f$.
It should be very easy to complete the proof after this point, since our first choice forces every other vertex to be a certain label.
I hope this helped!