If two graphs are isomorphic, they must have:
- the same number of vertices
- the same number of edges
- the same degrees for corresponding vertices
- the same number of connected components
I know that I've asked about an argument that proofs that number of vertices must be the same (bijection).
But I've made a mistake, cause my exercise was about cospectral graphs, like above. $C_{4}+$vertex and $K_{1,4}$. I know that there is no way that they are isomorphic cause first has degrees $(2,2,2,2,0)$ second $(1,1,1,1,4)$, but what is my mathematical argument to conclude that these graphs are not isomorphic ?
Best Answer
A more formal justification would argue that the multiset of vertex degrees is a graph invariant; that is, a property of the graph that is the same for every graph isomorphic to it. Since these two graphs have different multisets of vertex degrees, they cannot be isomorphic.
We can see that the multiset of vertex degrees is a graph invariant because an isomorphism always maps a vertex of degree d to another vertex of degree d. That can be directly argued from the definition of isomorphism.
Note that degree sequences of graphs are not an invariant, as the degree sequence may be permuted by an isomorphism.