graph theorygraph-isomorphism
Suppose I have two simple graphs $G(V,E)$ and $H(V,E)$ with number of vertices $N$. And $\forall i \quad \text{such that}\quad 0<i<N$
No:of elements in $V(G)$ with degree $i $ = No:of elements in $V(H)$ with degree $i$
Where $V(G)$ is the vertex set of $G$.
Given this can we say that $H$ and $G$ are isomorphic?
If they are not isomorphic. Then what is such a relation called?
One of them has a three cycle. They are both cubic graphs.
In simple terms, two graphs are isomorphic to each other so long as there is a bijection between the two vertex sets and such that the bijection preserves edges. That is, two graphs $G$ and $G'$ are isomorphic if there exists a bijection, $\phi: V(G) \to V(G')$, and if that bijection also preserves edges. Explicitly, this means that if $uv$ is an edge in $E(G)$, then $\phi (u) \phi (v)$ is an edge in $E(G')$.
One can visualize a graph isomorphism in two ways. 1. Start with a graph and move around vertices in what ever way you want while keeping all the edges in tact. The result, a graph that looks different, but isn't really. 2. A re-labeling of the vertices of $G$. This produces a graph that looks the same, but the vertices are called something else.
Automorphisms are a little bit trickier. The way I look at an automorphism is a moving around of vertices (while keeping edges in tact, as in (1) above) with the caveat that the graph must look exactly the same as before. For example, take $C_4$ with vertex set $V(G) = u_1,u_2,u_3,u_4$ and edge set $E(G) = u_1u_2,u_2u_3,u_3u_4,u_4u_1$ and consider the following bijection.
1. $\phi: V(G) \to V(G')$ where $\phi$ is the permuation $(u_1u_2u_3u_4)$ that sends $u_1 \to u_2$ $u_2 \to u_3$ $u_3 \to u_4$, and $u_4 \to u_1$. (If one is unfamiliar with cycle notation). This is an isomorphism since every edge is preserved, and indeed it is also an automorphism since the resulting graph looks exactly the same as the regular graph. (the permuation above is really just a rotation by 90 degrees if you lay out the original as a "square", as is tradition.
Best Answer
The two graphs $G$ and $H$ satisfying the condition you describe are said to have the same degree sequence. But this does not necessarily imply that the two graphs are isomorphic. It is possible to construct two graphs that have the same degree sequence but which are not isomorphic.
There is no known list of graph properties (be it the degree sequence, any other graph invariant, or even a combined list of such invariants) that provides a sufficient condition for two given graphs to be isomorphic.