0
$\begingroup$

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 .

$\endgroup$
  • 1
    $\begingroup$ What "following condition"?? $\endgroup$ – bof Apr 21 at 5:06
1
$\begingroup$

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):

Simple graph with six nodes, all of degree 3

( I plotted that using this website )

$\endgroup$
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.