Prove that the following properties: ‘There exists a vertex of degree 4’ and ‘There exists a cycle of length 4’ are preserved under isomorphism.

By definition, a property of a graph is said to be preserved under isomorphism if whenever G has that property, every graph isomorphic to G also has that property.

I know how reason about the first property, for example: since an isomorphism is a bijection between sets of vertices, isomorphic graphs must have the same number of vertices. If one graph has a vertex of degree 4, then another graph should also have a vertex of the same degree so they can be isomorphic. Thus, $v$ and $f(v)$ will have the same degree.

Would it be sufficient to say this for the first? I am not sure how to construct a formal proof for these properties. How can one prove the second property?


A graph isomorphism is a bijection, but it also preserves the edge relations between vertices. This is the main point of the exercise.

To illustrate, consider the degree $4$ vertex $u$. Since it has degree $4$, there are four vertices attached to it by edges, say those vertices are $v_1,v_2,v_3,v_4$. Then because $uv_1$ is an edge, and $f$ is an isomorphism, then $f(uv_1)$ is an edge between $f(u)$ and $f(v_1)$.

This argument is not complete yet. How do we know $f(u)$ is degree $4$ exactly? That is, it doesn't have more/less adjacent vertices than we expect.


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.