In a population of $n$ people, each person knows $k$ other people and each person is known by the same $k$ people. However, no two people, p1 and p2, know the same two people p3 and p4. What is the minimum $n$ such that this is possible for a given $k$? Or, in other words, what's the minimum number of nodes that must exist such that it is possible to connect each node to $k$ other nodes while not allowing a cycle of length 4?
Also, if it is possible, is there a program that can generate these graphs?
I don't have much on this problem yet besides a weak lower bound of $n\geq k^2-k+2$.
In the graphs below, an edge means that the two people it connects know each other. In 1), this is a demonstration of what we don't want, both A and C know D and B. In 2) these are configurations that work for k=2. For k=2, n=3 and all n>4 work. In 3) n=10, this is the smallest possible configuration for k=3.