Just to be clear, I made no conjecture. I was only asking when such graphs exist. —Dan Andy Latto wrote: ----- 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

???

I left out your definition of "homogeneous" (which is an interesting definition; I would be surprised if this concept didn't already exist in graph theory, possibly under some other name) because your conjecture is false even if you remove the word "homogeneous". if n and k are both odd, then you are looking for a graph with n+k+1 vertices, each of which has odd degree, which is impossible. -----