Prove that the property is preserved under isomorphism.

Question

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?

Answer 1

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.