An unlabeled graph is just an isomorphism class of graphs. I am trying to make a way to store an unlabeled graph in a computer without necessarily charactering it with a labeled graph.
For instance, take the labeled graph $G=(V,E)$, where $V=\{A,B,C,D\}$ and $E=\{\{A,B\},\{B,C\},\{B,D\},\{C,D\}\}$. Suppose I want to store this in a computer but without assigning labels to the vertex set, so I am merely storing the structure of the graph.
I know the degree sequence of $G$ is $D=(3,2,2,1)$. From here, I can create an multiset of 2-sets of $D$ that corresponds the edges in $G$: $E'=\{\{1,3\},\{2,3\},\{2,3\},\{2,2\}\}$. Note every 2-set in $E'$ is an edge in $G$, but written in terms of the degrees of the adjacent vertices, rather than the indices of the adjacent vertices. In other words $\{u,v\} \in E \iff \{\deg u, \deg v\} \in E'$.
It is clear any graph isomorphic to $G$ will have this same $E'$.
Is it true that every unlabeled graph will have a unique $(D,E')$?
Is this a way to uniquely characterize every unlabeled graph? If not, am I missing something?
Best Answer
This approach will not work: in particular, any two $k$-regular $n$-vertex graphs will have the same multiset with $\{k,k\}$ occurring $\frac{kn}{2}$ times. The complete bipartite graph $K_{3,3}$ and the skeleton of a triangular prism are both $3$-regular graphs on $6$ vertices; these are just one of many pairs of graphs you will not be able to distinguish.
In general, if you were hoping for an easy way to do this, you're out of luck, because it would correspond to an easy way to check if two graphs are isomorphic. (We don't currently know of a polynomial-time algorithm to do this.)
If you are looking for a way to do this with software, a graph isomorphism tool such as bliss or nauty can generate a "canonical labeling" for a graph, which will be the same for two isomorphic graphs.