# Proof that graphs are not isomorphic 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 ?

• The argument that they have different degree sequences seems like a fine argument to me -- is there some reason it doesn't satisfy you? Nov 9, 2015 at 0:09
• I don't know if it is enough. Maybe I'm supposed to use more sophisticated terms. I don't know. Is it enough ? Nov 9, 2015 at 0:16
• Two graphs are isomorphic if they are essentially the same graph. So if two graphs are the same (isomorphic), then there degree sequences are the same as otherwise we would have a different graph. So having different degree sequences is definitely enough to show two graphs aren't isomorphic.
– Ben
Nov 9, 2015 at 1:02