How to prove a property is preserved under isomorphism?

Question

I'm following along an MIT discrete maths course. One problem is as follows:

Determine which among the four graphs pictured in the Figures are isomorphic. If two of these graphs are isomorphic, describe an isomorphism between them. If they are not, give a property that is preserved under isomorphism such that one graph has the property, but the other does not. For at least one of the properties you choose, prove that it is indeed preserved under isomorphism (you only need prove one of them).

(source - MIT open courseware 6-042j, assignment 4)

So, let's just consider graph G1 and G2. From examination I would say there is one additional edge in G2 that's not present in G1, so no isomorphism exists. The problem says:

If they are not [isomorphic], give a property that is preserved under isomorphism such that one graph has the property, but the other does not. For at least one of the properties you choose, prove that it is indeed preserved under isomorphism […]

How to proof that? And one more question, how do you usually go about finding isomorphims between graphs? Write down all the edges from one graph and see if they are present in the other?

Answer 1

For $G_1$ and $G_2$, they are not isomorphic as every vertex in $G_1$ has degree $3$ but vertex $10$ in $G_2$ has degree $4$.

If they are isomorphic, then they should share the same degree.

To prove that they are not isomorphic, look for graph invariant that are not obeyed, for example

(a) degree,

(b) number of edges,

(c) number of components,

(d) cycle length.

Since graph isomorphism means a relabeling of vertices to match a graph, the above properties are preserved.

To prove that two graphes are isomorphic, construct a bijection between the nodes and check that they are connected in the same way.

Complexity wise:

According to wikipedia page of graph isomorphism, in November 2015, László Babai, a mathematician and computer scientist at the University of Chicago, claimed to have proven that the graph isomorphism problem is solvable in quasi-polynomial time. This work has not yet been vetted. In January $2017$, Babai shortly retracted the quasi-polynomiality claim and stated a sub-exponential time time complexity bound instead. He restored the original claim five days later.

Answer 2

No-one seems to have answered your question about how to prove that the properties under isomorphism are preserved, so I thought I'd give it a go. Hopefully you've figured it out by now, but it might be useful for future fellow 6.042ers

---

The formal definition of isomorphism between two graphs $G$ and $H$ (and indeed, the one provided by the book) is a bijection $f\ :\ V(G) \rightarrow V(H)$ such that,

$\langle u — v \rangle \in E(G) \Leftrightarrow \langle f(u) — f(v) \in E(H) \rangle$

for all $u, v \in V(G)$

This means an isomorphic function is applied to any given node in $G$ to get the corresponding node in $H$. It also means the edge between any two nodes in G is also preserved in H.

That is to say, if $u$ is adjacent to $v$ in $G$, then $f(u)$ is adjacent to $f(v)$ in $H$. This means the number of edges does not increase or decrease while performing the isomorphism.

Since the number of edges does not change, it follows that the max degree must also remain the same.$\blacksquare$

Answer 3

For edges you can give mapping between edges for example f(9)=7,f(8)=9,f(7)=8,f(i)=i for others. And give an edge which in between vertices of first graph and not in second graph. You should write "a property not preserved under mapping then this mapping is not isomorphism" since if you have already took it isomorphism then what is their to proof? And for an isomorphism both graph should have same no. Of edged as well as same no. Of vertices,so always start with that,sometimes giving a mapping is tough when graphs are very complicated and big.

Answer 4

$G_2$ has fourteen edges, while the others each have fifteen edges. So $G_2$ is not isomorphic to the others.

Of the others, $G_4$ looks particularly simple. It's clear that it has cycles of length four. Indeed each vertex is in two length four cycles. Do either of $G_1$ and $G_3$ share this property?