Re: [math-fun] Graph question
Dan Asimov <dasimov@earthlink.net> wrote:
Find a connected graph G on a countably infinite set of vertices such that * each vertex has infinite valence * each vertex is non-adjacent to exactly 2 vertices * any isomorphism of a subgraph H_1 to a subgraph H_2 extends to an isomorphism of the entire graph G to itself.
Note: By a "subgraph" here is mean any collection of the vertices and any collection of the edges which together form a connected graph.
If I understand you correctly, I think the graph that links each integer n to every other integer except n-1 and n+1 would be a solution.
The subgraphs induced by {1, 3} and {1, 5} are isomorphic, but there's no automorphism of the whole graph which converts one into the other. The only solution I can find is 'the complement of the disjoint union of countably many copies of K3'. -- APG.
Sent: Friday, May 15, 2020 at 7:24 PM From: "Keith F. Lynch" <kfl@KeithLynch.net> To: "math-fun" <math-fun@mailman.xmission.com> Subject: Re: [math-fun] Graph question
Dan Asimov <dasimov@earthlink.net> wrote:
Find a connected graph G on a countably infinite set of vertices such that * each vertex has infinite valence * each vertex is non-adjacent to exactly 2 vertices * any isomorphism of a subgraph H_1 to a subgraph H_2 extends to an isomorphism of the entire graph G to itself.
Note: By a "subgraph" here is mean any collection of the vertices and any collection of the edges which together form a connected graph.
If I understand you correctly, I think the graph that links each integer n to every other integer except n-1 and n+1 would be a solution.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
On Fri, May 15, 2020 at 2:25 PM Keith F. Lynch <kfl@keithlynch.net> wrote:
Dan Asimov <dasimov@earthlink.net> wrote:
Find a connected graph G on a countably infinite set of vertices such that * each vertex has infinite valence * each vertex is non-adjacent to exactly 2 vertices * any isomorphism of a subgraph H_1 to a subgraph H_2 extends to an isomorphism of the entire graph G to itself.
Note: By a "subgraph" here is mean any collection of the vertices and any collection of the edges which together form a connected graph.
If I understand you correctly, I think 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
participants (3)
-
Adam P. Goucher -
Andy Latto -
Keith F. Lynch