Fascinating! Thanks, Adam. Now I wonder the same thing if n and k are allowed to be infinite. If one or both are countable, that would go a long way. How about countable valence & every vertex non-adjacent to exactly 2 vertices? Dan ----- Wikipedia gives a complete classification of these graphs: https://en.wikipedia.org/wiki/Homogeneous_graph#Classification which implies that the answer to your question is 'precisely when (n, k) is one of the following tuples': (0, 0); (2, 2); (4, 4); (a-1, ab) where a and b are positive integers; (ab, a-1) where a and b are positive integers.

Sent: Thursday, May 14, 2020 at 5:48 PM From: "Andy Latto" <andy.latto@pobox.com> To: "Dan Asimov" <dasimov@earthlink.net>, "math-fun" <math-fun@mailman.xmission.com> Subject: Re: [math-fun] Graph question

On Thu, May 14, 2020 at 11:02 AM Dan Asimov <dasimov@earthlink.net> wrote:

...

Question: --------- Given a pair of positive integers (n,k), when does there exist a homogeneous graph G such that

* every vertex has valence n, and

* every vertex has just k vertices that are not adjacent to it

???