Sorry! Just found this in my drafts folder; apparently I forgot to hit send. On Fri, May 15, 2020 at 8:41 PM Dan Asimov <dasimov@earthlink.net> wrote:
At the risk of sounding stupid, I'd like to see a proof of the claim (that the isomorphism of the subgraphs taking 1—>1, 2—>2, 4—>5, 5—>6 does not extend to an isomorphism G —> G).
Suppose F was the desired isomorphism. F(1) = 1, and F(2) = 2, by hypothesis. Since there is no edge between 2 and 3, there must be no edge between F(2) and F(3). So F(3) must be either 1 or 3. But if F is isomorphism, hence injective, and F(1) = 1, so F(3) = 3. But now there is an edge between F(3) = 3 and F(4) = 5, and no edge between 3 and 4, so F is not an isomorphism. QED. Andy
Andy Latto wrote: -----
... the graph that links each integer n to every other integer except n-1 and n+1 would be a solution.
I don't think this works. The induced subgraph on {1,2,4,5} is isomorphic to the induced subgraph on {1,2,5,6}, using the isomorphism that fixes 1 and 2, sends 4 to 5 and 5 to 6. But this does not extend to an isomorphism of G to G. -----
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Andy.Latto@pobox.com