discrete mathematicsgraph theorygraph-isomorphism
I've seen definitions stating that
"If $G=(V,E)$ and $G'=(V',E')$ , then a mapping $\theta : V \rightarrow V'$ is an isomorphism if, for all $u,v \in V$,
$uv \in E$ if and only if $\theta (u) \theta (v) \in E'$. "
This definition makes little (applicable) sense to me. Geometrically speaking, what is an isometric tree, and how is it different to a non-isomorphic tree?
Here is an example of two non-isomorphic graphs that are at distance $0$ by your definition:
Both graphs have $6$ vertices, all of degree $3$. But the left one is $K_{3,3}$, a bipartite graph; the right one is not bipartite because, in particular, it has two clearly visible triangles. This is one way to see that they're not isomorphic. (You can also look at their complements; the complement of the right graph is connected and the complement of the left graph isn't.)
In general, for large $k$ and $n$, if there are any $k$-regular graphs on $n$ vertices, there are lots.
One measure I might suggest is "edit distance" between two graphs: the number of times you need to perform some well-defined operation (for example, adding or removing an edge or an isolated vertex) to turn one graph into something isomorphic to the other.
I just found an example in the graph reconstruction literature (thanks Bob Krueger) of two non-isomorphic graphs that have the same multiset of spanning trees, in Sedlacek, J. (1974). The reconstruction of a connected graph from its spanning trees. Mat. Casopis’Sloven. Akad. Vied. 24, 307-314. They are depicted below.
Also, they can be distinguished by their decks of node-deleted subgraphs, as the left graph has an 8-cycle as a node-deleted subgraph, while the right graph does not.
Best Answer
In loose terms, two graphs $G$ and $H$ are said to be isomorphic if there is a way to "draw" the graph $G$ to look like $H$.
For example, consider the claw graph $K_{1,3}$ and the path $P_4$ with 3 edges. These graphs are both trees, but they are said to be non-isomorphic because there is no way to move around the vertices and edges of $K_{1,3}$ to obtain the path $P_4$.
In general for larger graphs, it is very difficult to determine if two graphs are isomorphic.
Consider the two graphs pictured below.
While these graphs look very different at first glance, they are actually isomorphic! This can be seen by the labeling of the vertices: if we move all of the vertices of one graph to have the same positions as pictured in the other graph, we will actually be looking at the same graph! (The are two different drawings of the Petersen Graph)