# Ulam's Conjecture, Graph isomorphism, Application

Here is a short takeout on Ulam's Conjecture: On the Wikipedia page it say it has been proven up to n=11.

Now the Question: If I have to check for the Isomorphism, does this mean, if I take out an Vertex x in Graph one and then show that for all vertices in Graph two it is impossible to get G-x, then they could not be isomorphic? As long I am have less the 11 edges. Any suggestion on this?

If you take out a vertex from the first graph, leaving $G-x$, but you can't find any isomorphism between $G-x$ and $H-y$ for any $y \in V(H)$, then $G$ and $H$ are definitely not isomorphic. (If there were an isomorphism $\phi$, then $H - \phi(x)$ would be isomorphic to $G-x$.)
• @thetha Consider the statements $(P)$ "graphs $G$ and $H$ are isomorphic" and $(Q)$ "the sets $\{G-x:x\in V(G)\}$ and $\{H-y:y\in V(H)\}$ are essentially the same" (the 'essentially' referring to isomorphism). Then it should be clear that $$(P) \implies (Q),$$ which is pertinent to your question. Ulam's conjecture states that $$(Q) \implies (P).$$ Commented Jul 31, 2017 at 17:31
• @thetha If two graphs are isomorphic, then they are essentially the same object. Take $G$ to be the cycle $C_5$, for example, and suppose that $H$ is isomorphic to $G$. Then $H$ is also (a different copy of) $C_5$, and both graphs should behave the same way. Deleting any vertex of $G$ results in the path $P_4$; similarly, deleting any vertex of $H$ leaves $P_4$. Now, suppose we had a third graph $J$ on five vertices, and suppose that for some vertex $v$, it turns out that $J-v$ is not isomorphic to $P_4$. Then $G$ and $J$ are not isomorphic to each other. You don't need Ulam for this! Commented Jul 31, 2017 at 22:13