For what n,m the following conditon hold

Question

Suppose their are n people and each person is friend with exactly m other people . What should be the relation between n and m for the following condition to hold and how to prove that .

For example - for m = 3 i.e a person can be friends with exactly 3 other people i think n should be multiple of four . I visualized it by considering group of people as corners of square and lines between them denoting friendship .

Answer 1

You are considering a graph with $n$ vertices, where each vertex has degree $m$. That is, you are considering a graph with a length $n$ degree sequence $(m,m,\cdots,m)$. I am assuming that a person cannot be friends with themselves, they cannot be 'twice' friends with another, and all friendships are reciprocal. Then you are considering undirected graphs without loops or multi-edges, i.e. simple graphs. Then consider the Erdős–Gallai theorem which tells you that a choice of $(n,m)$ works if and only if $nm$ is even, and $$\sum_{i=1}^k d_i \leq k(k-1) + \sum_{i=k+1}^n \min(d_i,k),$$ for each $k$ in $1\leq k\leq n$. But for $k\leq m$ this is just $$km\leq k(k-1)+k(n-k)$$ and for $m<k$ this is just $$km\leq k(k-1)+ m(n-k).$$

For $k\leq m$ this just says $m\leq (k-1)+(n-k)= n-1$ and for $m<k$ it says: $$km\leq k^2-k+mn-mk\implies m\leq \frac{k(k-1)}{2k-n}.$$

Additionally, we know that $nm$ is even, and thus one of $n$ and $m$ must be even (or both).

Also, using the Havel-Hakimi algorithm we can construct such a graph for $n=6$ and $m=3$ (contradicting your $4|n$ claim):

( I plotted that using this website )

Answer 2

I guess you are asking: for which integers $n\ge1$ and $m\ge0$ does there exist an $m$-regular graph of order $n$, that is, a graph on $n$ vertices in which each vertex has degree $m$?

The obvious necessary conditions are that $n\gt m$ and $mn$ is even. These conditions are also sufficient. Let the vertices be $n$ equally spaced points on a circle. If $m\lt n$ and $m$ is even, join each vertex to the $\frac m2$ nearest vertices on either side. If $m\lt n$ and $m$ is odd and $n$ is even, join each vertex to the diametrically opposite vertex and to the $\frac{m-1}2$ nearest vertices on either side.

There are two $2$-regular graphs of order $6$, namely, the cycle graph $C_6$ and the graph $C_3+C_3$ consisting of two disjoint triangles. The complement of either of those graphs will be a $3$-regular graph of order $6$. The complement of $C_6$ is the graph shown in Alex Clark's answer; the complement of $C_3+C_3$ is the complete bipartite graph $K_{3,3}$.