Graph Isomorphism Query: Analyzing Two Graphs for Isomorphism and Proving Non-Existence of Vertex Isomorphism

Let us consider these two graphs (on the left and on the right):

Are they isomorphic to each other? I think not because, even though they have the same number of nodes, edges, and the same distribution of degrees, the second one is a disconnected graph.

But if I am correct, how can I prove that there is no isomorphism between the vertices of the two graphs? (see the last comlumn of the first table in this Wikipedia link Graph isomorphism)

Prove that if $$G_1$$ is not connected and $$G_2$$ is connected, then they cannot be isomorphic

Assume, for the sake of contradiction, that there exists an isomorphism $$\varphi: G_1 \to G_2$$ between the two graphs.

Since $$G_1$$ is not connected, there exist at least two disconnected components, say $$C_1$$ and $$C_2$$, in $$G_1$$. Without loss of generality, let's assume that $$\varphi(C_1)$$ and $$\varphi(C_2)$$ are the corresponding components in $$G_2$$.

Now, since $$\varphi$$ is an isomorphism, it preserves connectivity. However, $$G_2$$ is connected, which means that $$\varphi(C_1)$$ and $$\varphi(C_2)$$ must also be connected components in $$G_2$$.

This leads to a contradiction, as $$G_2$$ cannot have disconnected components if it is connected. Therefore, our assumption that there exists an isomorphism between $$G_1$$ and $$G_2$$ is false.

Consequently, if $$G_1$$ is not connected and $$G_2$$ is connected, then $$G_1$$ and $$G_2$$ cannot be isomorphic.

You basically already answered your question. As with every other field of math, we call two mathematical objects of the same type isomorphic if they "behave" the same. In the case of graph isomorphisms, this amounts to the graphs differing only by their "labels" (i.e. what we call the vertices). Things such as connectivity are then of course invariant under isomorphisms: Given an isomorphism $$\varphi \colon V(G) \to V(H)$$, a path $$v_1, v_2, \dots, v_n$$ in $$G$$ would map to a path $$\varphi(v_1), \varphi(v_2), \dots, \varphi(v_n)$$ in $$H$$. Indeed, all of the vertices remain distinct as $$\varphi$$ is injective and adjacency is preserved by definition.

So, if $$G$$ is connected, then $$H$$ is connected as well: For $$a,b \in V(H)$$, we can find a $$\varphi^{-1}(a)$$-$$\varphi^{-1}(b)$$-path in $$G$$ as $$G$$ is connected and $$\varphi$$ is surjective, which then induces an $$a$$-$$b$$-path in $$H$$.

Hence, the two graphs are indeed non-isomorphic.

Comment to your proof: I think there is a lot of confusion floating around given what you have written.

The first paragraph is fine.

The second paragraph is already iffy. First, you technically need to define what you mean by $$\varphi(C_1)$$ and $$\varphi(C_2)$$. Also, calling them "corresponding components" is confusing. Usually, components is just used as a short-term for connected components. So, this is only valid if you knew that connected components of $$G_1$$ get mapped by $$\varphi$$ to connected components of $$G_2$$ which is a stronger statement than the claim you are trying to prove.

The third paragraph is now really confusing. If you already use the fact that $$\varphi$$ preserves connectivity, then the proof is essentially a one-liner: If $$G_1$$ were isomorphic to $$G_2$$, i.e. there is some isomorphism $$\varphi\colon G_2 \to G_1$$, then $$G_1$$ needs to be connected as $$G_2$$ is connected and $$\varphi$$ an isomorphism. This contradicts the fact that $$G_1$$ is not connected.

In some sense, this should be the goal of your proof to show this! The next sentence is even more confusing: You already (presumably) know that $$\varphi(C_1)$$ and $$\varphi(C_2)$$ are connected components of $$G_2$$, it is not a consequence of $$G_2$$ being connected.

The fourth and fifth paragraph are again sensible.

• Ok that, perhaps I understand. Let me modify my question with a proposed solution
– Mark
Commented Jan 8 at 15:06
Let me mention a fundamental concept relevant here. A graph invariant (also called graph property) is a map $$\phi$$ that assigns a number or some other object to a graph, in a way that is invariant under isomorphism, i.e., such that $$\phi(G_1)=\phi(G_2)$$ if $$G_1$$ and $$G_2$$ are isomorphic. There is an abundance of such graph invariants, for example the chromatic number, the maximal edge degree, the girth, and the diameter, to mention a few.
{"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 60, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0, "url": "https://math.stackexchange.com/questions/4840642/graph-isomorphism-query-analyzing-two-graphs-for-isomorphism-and-proving-non-ex", "fetch_time": 1721901831000000000, "content_mime_type": "text/html", "warc_filename": "crawl-data/CC-MAIN-2024-30/segments/1720763857355.79/warc/CC-MAIN-20240725084035-20240725114035-00648.warc.gz", "warc_record_offset": 333306315, "warc_record_length": 38847, "token_count": 1200, "char_count": 4413, "score": 3.828125, "int_score": 4, "crawl": "CC-MAIN-2024-30", "snapshot_type": "latest", "language": "en", "language_score": 0.9170544147491455, "file_path": "/sailhome/yjruan/project/latent-lm/data/processed/finemath-4plus/finemath-4plus/train-00018-of-00064.parquet"}