On Sat, May 16, 2020 at 2:51 PM Keith F. Lynch <kfl@keithlynch.net> wrote:
Dan Asimov <dasimov@earthlink.net> wrote:
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).
Without my taking a position on whether my first solution is valid, here's an alternative solution:
The countably infinite vertex set consists, not of all integers, but of all rationals except 0, 1, and -1. Each vertex x is connected to every other vertex except -x and 1/x.
This graph, the complement of the union of countably many squares, doesn't work. There is an edge between 2 and -1/2, and between 2 and 3, so the map from {2,-1/2} to {2 , 3} given by F(2) = 2, F(-1/2) = 3 is an isomorphism between two graphs, each with 2 vertices joined by an edge. But this isomorphism F does not extend to an isomorphism G->G. Proof: If F was such an isomorphism, Since -2 is adjacent to neither 2 or -1/2. F(-2) must be adjacent to neither F(2) nor F(-1/2). But there is no vertex that is adjacent to neither 2 nor 3. The complement of a G' is the greph with the "opposite" set of edges and the same set of vertices. That is there is an edge in G' between V1 and V2 just if there is no edge between V1 and V2 in G. A map of vertices is an isomorphism of G exactly if it is an isomorphism of G', so homogeneity is maintained by complementation. In constructing the counterexamples I posted, I found it much easier to reason about the complements of the suggested graphs, rather than the graphs themselves, since I find graphs where the vertices all have degree 2 much easier to visualize than graphs where every vertex is connected to all but 2 other vertices. Andy
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Andy.Latto@pobox.com