1
$\begingroup$

enter image description here

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 ?

$\endgroup$
  • 4
    $\begingroup$ The argument that they have different degree sequences seems like a fine argument to me -- is there some reason it doesn't satisfy you? $\endgroup$ – Gregory J. Puleo Nov 9 '15 at 0:09
  • $\begingroup$ I don't know if it is enough. Maybe I'm supposed to use more sophisticated terms. I don't know. Is it enough ? $\endgroup$ – Filip Kowalski Nov 9 '15 at 0:16
  • 1
    $\begingroup$ 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. $\endgroup$ – Ben Nov 9 '15 at 1:02
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.