Is the picture isomorphic?

Question

enter image description here Me and my frined were having a descussion i think this is not isomorphic. What do you think and could you provide some more info about it?

Answer 1

Let $G=(V,E)$ and $G‘=(V’,E‘)$ be two graphs. They are isomorphic if there is a bijection $\varphi: V \to V‘$ such that $(v_x, v_y) \in E \iff (\varphi(v_x), \varphi(v_y)) \in E‘$.

This means that, if we can find a bijective vertex mapping between $V(G)$ and $V(G‘)$, such that adjacency is preserved, then the given graphs are isomorphic. Can you go from here for the provided graphs?

Edit: The number of vertices, the number of edges, the degree sequence. and many more other properties must be the same in $G$ and $G‘$ in order for them to be isomorphic. These are necessary conditions. Take the number of vertices and edges, this follows directly from the defined isomorphism map. But these conditions are not sufficient, meaning you can have graphs having the same number of vertices and edges without them being isomorphic. We need a so called certificate in order to prove isomorphism (have a look at canonical labelling). However the complexity of the graph isomorphism problem is high (actually a precise classification is still missing, but we do not have efficient algorithms for general graphs).

Meaning, finding certificates such as canonical labellings is not faster for a small number of graphs than finding the isomorphism map directly. Since your provided problem is very easy, you should construct the isomorphism map directly.

For example: let $\varphi(v_5)=u_5$. Define the other mappings such that the definition provided is satisfied. (and of course, if some necessary condition fails, you can already state that the two graphs are not isomorphic).