Non isomorphism graph

Question

Im confused what is non isomorphism graph

• cant post image so i upload it on tinypic Particulary with this example

It is said, that this c4 graph on left side is non isomorphism graph. But this is my try to make it isomorphic, like u might see it on picture

I have idea of non isomorphism graph, with contradiction, that u can for every graph, "squeeze" it, move little left-little right branches and vertices, mark vertices with different numbers, make bijection which shows that u can translate base graph to that derived , the end?

Can u give me some examples with non isomorph. graphs, and explanation that contradict mine?

*all down votes are not welcome, leave comment for discussion if u want to down vote

Answer 1

Formally, (simple) graphs are an ordered pair $(V,E)$ where $V$ is a set (the vertex set) and $E$ has a set of $2$-subsets of $V$.

So, a $4$-cycle graph really is a pair $(V,E)$ with:

• Vertex set: $V=\{1,2,3,4\}$,
• Edge set: $E=\{\{1,2\},\{2,3\},\{3,4\},\{1,4\}\}$.

There is no drawing here.

We often draw graphs to make them easier to visualize (and because graph drawings are interesting in their own right). I might draw the graph like this:

Someone else might draw it like this:

These are two different drawings of the same graph. I.e., the graphs are equal. (Despite being drawn differently.)

---

Graph isomorphism is instead about relabelling. In this setting, we don't care about the drawing.=

Typically, we have two graphs $(V_1,E_1)$ and $(V_2,E_2)$ and want to relabel the vertices in $V_1$ so that the edge set $E_1$ maps to $E_2$. If it's possible, then they're isomorphic (otherwise they're not).

For example:

These two graphs are

• not equal, e.g., only one of the graphs has the edge $\{1,4\}$, so they have different edge sets, but they are

• isomorphic, if we swap the vertex labels $3$ and $4$, we go from the left graph to the right graph.

So...

I have idea of non isomorphism graph, with contradiction, that u can for every graph, "squeeze" it, move little left-little right branches and vertices, mark vertices with different numbers, make bijection which shows that u can translate base graph to that derived , the end?

The part "mark vertices with different numbers" is what isomorphism is about. If they're isomorphic, you can:

1. Relabel the vertices of one to make it equal to the other.

After which we can

2. Redraw two equal graphs however we like (or even create a video showing how one maps to the other). But this is about visualization, i.e., making it easier to see and understand.