# For what n,m the following conditon hold

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 .

• What "following condition"?? – bof Apr 21 at 5:06

## 2 Answers

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 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 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 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}$$.