Proof of the maximum number. Consider a graph with its vertices the people, and if two people are friends, a red edge between them, while if they are not friends, a blue edge between them. Let $k$ be the maximum number of blue edges, so for each of these edges there exist at least $2$ red edges, and we count each red edge at most $n-2$ times. We thus have $k+\frac{2k}{n-2}\le \binom{n}{2}$, therefore $k\le \binom{n-1}{2}$.

mahanmath wrote:

could you please explain me what to do after? i cant continuou

Sorry to waking up an old topic, but is my solution is right?

This problem is nice (and easy!) I have a connected problem: Find the maximum number of sets of 3 people such that there are exactly 2 acquaintance relationship among them.

I claim that the answer is $\binom{n-1}{2}$. Denote the maximal possible number as a function of $n$, i.e. $f(n)$. Easily prove that $f(3) =1$. We claim that $f(n) \le f(n-1) + n-2$. Start with a group of $n-1$ people, and we bring in a new one. If a new person does not know anyone, we would have no new pairs. If a new person knows $d \ge 1$ people, then we would have at most $n-1-d$ pairs. Therefore, we have $f(n) \le f(n-1)+n-2$ as required. This gives us $f(n) \le \binom{n-1}{2}$. However, $f(n) \ge \binom{n-1}{2}$ - take a person $A$ and let $A$ know everyone else. Also, let every other $n-1$ people know only $A$, but not other $n-2$ people. This gives $f(n) \ge \binom{n-1}{2}$. Therefore, the answer is $\binom{n-1}{2}$ as claimed.

Another approach: We give the "star" example to see that $n-1 \choose 2$ is attainable. Next, suppose that there are more than $n-1 \choose 2$ pairs with the property. Let us call this set of pairs $S$. We will provide a lower bound on the number of edges in the graph. Note that each pair $(u, v)$ in $S$ contributes exactly 2 edges by definition. This means that as a whole we have $(n-1)(n-2)$ edges "induced" by pairs in $S$ (with some repetitions). Let us call this multiset $Z$. Now, consider one edge $(u,v)$ of the $(n-1)(n-2)$ edges of $Z$. We argue that $(u,v)$ can be repeated at most $n-2$ times in $Z$. To see why, suppose for the sake of contradiction that $(u,v)$ is repeated at least $n-1$ times. Since $(u,v)$ is an edge induced by a pair in $S$, this means there is a vertex $w_i$ (distinct from $u$ and $v$) adjacent to exactly one of $u$ or $v$ (but not both). Note that $w_i$ must exist for each occurrence of edge $(u,v)$ in $Z$. In fact, the $w_i$ must be pairwise distinct: if not, then there would be an edge present between $u$ and $w_i$ (WLOG) and not present between them so contradiction (this is easy to see). But then there are at least $n-1 + 2 = n+1$ vertices in the graph which is a contradiction. Thus, each edge is repeated at most $n-2$ times in $Z$. Then, the number of distinct edges in $Z$ is at least $\frac{(n-1)(n-2)}{(n-2)} = n-1$. This in turn means that there are at least $n-1$ distinct edges in the graph. These edges form pairs that cannot possibly be in $S$. If we add up the number of pairs of vertices in $S$ and not in $S$ we get strictly more than $n-1\choose 2$ + $n-1$ = $n \choose 2$ pairs of vertices in the graph. This is a contradiction because there are exactly $n \choose 2$ total pairs.

Let $P(n)$ be the desired function of $n$. We proceed by strong induction. Claim that $P(n)=\tbinom{n-1}{2}$. Base case ($n=0$) is trivial. Now, by the construction mentioned above, we have $P(k)\geq \tbinom{k-1}{2}$. In that construction, every non-edge contributes to $P(k)$, so the only way to get a "better" construction would be to have less than $k-1$ edges. In particular, we can separate the graph into connected components of size $x_1,x_2,\dots,x_h<k$. Because pairs of vertices in different components cannot contribute to $P(k)$, and $\tbinom{k-1}{2}\geq \sum \tbinom{x_i-1}{2}$ by convexity, we conclude the result $\blacksquare$

rkm0959 wrote: I claim that the answer is $\binom{n-1}{2}$. Denote the maximal possible number as a function of $n$, i.e. $f(n)$. Easily prove that $f(3) =1$. We claim that $f(n) \le f(n-1) + n-2$. Start with a group of $n-1$ people, and we bring in a new one. If a new person does not know anyone, we would have no new pairs. If a new person knows $d \ge 1$ people, then we would have at most $n-1-d$ pairs. Therefore, we have $f(n) \le f(n-1)+n-2$ as required. This gives us $f(n) \le \binom{n-1}{2}$. Why is this true? I think this is a counter-example: Suppose our $n-1$ group of people have no connections between them. Bring in a new person who knows everyone in the group. Then we go from $0$ pairs to $\binom{n-1}{2}$. We clearly form more than $n-1-(n-1)$ pairs.

Here is a different approach:We claim the answer is $\binom{n-1}{2}$.For an example we can consider a star graph for example.For proving this is optimal we use strong induction on $n$.Since every edge produces a "bad" pair the claim is true if we have more than $n-2$ edges otherwise the graph is disconnected and we will be trivially done by Kramata's inequality.

Regard it as a graph; adding an edge between two different connected components cannot decrease the number of such pairs, so we can assume the graph is connected. Then it has at least $n-1$ edges, so at most $\frac{(n-1)(n-2)}{2}$ disconnected pairs, so our number is not larger. To see it works, just connect one vertex to all the others.

Let $g(n)$ be the maximal number of described pairs in a connected graph with $n$ vertices, and let $f(n)$ be the maximal number in a not necessarily connected graph with $n$ vertices. Obviously, $f(n)\geqslant g(n)$ for all $n \in \mathbb N$. Furthermore, $g(n)={ n-1 \choose 2}$ for all $n \in \mathbb N$, because we can achieve this number with a graph where $n-1$ vertices have degree $1$ and one vertex has degree $n-1$, and we cannot achieve any bigger number because we would then have less than $n-1$ edges and our graph wouldn't be connected. Now, consider a graph with $n$ vertices with $f(n)$ described pairs. Suppose it has $k$ connected components. Let $x_1, x_2, \ldots ,x_k$ be the sizes of these components. Then $f(n)=\sum_{j\leqslant k} {x_j-1 \choose 2}$ because components don't affect each other, so every component has maximum amount of described pairs. However, we have ${x-1 \choose 2}+{y-1 \choose 2}\leqslant{x+y-1 \choose 2}$ for all pairs of positive integers $x,y$. Repeatedly applying this inequality to the expression for $f(n)$, we obtain $f(n)\leqslant { n-1 \choose 2 }=g(n)\leqslant f(n) \implies f(n)={ n-1 \choose 2 }$.

Consider the obvious graph theoretic interpretation.Call such a pair of vertices sweet pair. We claim that the maximum possible value is $\binom{n-1}{2}$.For construction , consider an $n-$ tree and all vertices connected to one vertex. Let $G_i$ be a connected component of $G$ with no. of vertices $a_i$ .Then we already have a construction for $\binom{a_i-1}{2}$ sweet pairs .Note that the number of seet pairs in this connected component cannot be greater than $\binom{a_i-1}{2}$ because then $$\text{No of edges } < \binom{a_i}{2}-\binom{a_i-1}{2}=a_i-1$$Contradiction. So maximum number of sweet pairs in the total graph $G$ with $t$ connected components is $$\sum_{i=1}^{t} \binom{a_i-1}{2}$$But since $\{n-t,0,0,....,0\}$ majorises $\{a_i-1\}$ by Karamatas we get that $$\sum_{i=1}^{t} \binom{a_i-1}{2} \leq \binom{n-t}{2} \leq \binom{n-1}{2} $$Done

Isn't this trivial??? Call a pair of vertices bad if they don't satisfy the condition. We'll prove that there are at least $n-1$ bad pairs. Case 1: The graph is connected. It has at least $n-1$ edges, and a pair of vertices with an edge is obviously bad. Done. Case 2: The graph is not connected. Consider any connected component $A$. If we pick vertices $a \in A$ and $b \notin A$, a pair $\{a,b\}$ is obviously bad, so there are at least $|A|(n-|A|)$ bad pairs. The function $f(x)=x(n-x)$ for $x \in [1,n-1]$ has minimum value of $n-1$ at $x=1$ and $x=n-1$. Done.

Solution The pairs which fit the definitions of the problem must share at least 1 acquaintance. To be optimal, it has to be exactly 1 person. This works because if they share more than 1 persons, they lose 2k possible connections for each additional person shared, less than the original amount. Now we show that the most optimal construction involves one person shared among all the other people, while none of the others are acquainted with each other. Just sharing 1 person means there are (n-1) choose 2 ways. If we have 2 people, and k goes to one group while (n-2-k) goes to the other. Then by choose function this is definitely less than (n-1) choose 2. So the 1 case is the optimal. Therefore the answer is n-1 choose 2 My proof is probably full of issues so please correct them.

The answer is ${n-1}\choose {2}$. This can be achieved by having one person be friends with all other people, while no other friendships occur. If the graph is connected, it has at least $n-1$ edges. Since a pair of friends is always bad, there are at most ${{n}\choose {2}}-(n-1)={{n-1}\choose {2}}$ good pairs. If the graph is not connected, then two people from different connected components cannot be good, since they do not have any common friends (otherwise they would be in a connected component), so our total answer is just the sum of the answers for each connected component. Thus, if the connected components have size $a_1\cdots a_m$ for $m\geq 2$, there are at most $$\sum_{i=1}^m {{a_i}\choose 2}$$good pairs. By Karamata, as the sum of $a_i$ is equal to $n$, $$\sum_{i=1}^m {{a_i}\choose 2}\leq 1({{(n-m+1)}\choose 2})+(m-1)({1\choose 2})={{(n-m+1)}\choose 2}\leq {{(n-1)}\choose 2},$$as desired.

Answer is $\binom{n-1}{2}$ with the example star graph where a vertex is connected to all the other vertices and there doesn't exist any edge in rest of the graph. Let $G$ be the graph. Assume that there are $\geq \binom{n-1}{2}+1$ such pairs. Draw blue edges between those pairs. \[\sum{\text{blue}\deg} \ v_i\geq 2(\binom{n-1}{2}+1)=n^2-3n+4\]Hence if $A$ has maximum degree among blue edges, then $\text{blue} \ deg \ A\geq n-2$. If $\text{blue} \ \deg \ A=n-1,$ then $A$ cannot have a "real" edge which restricts $A$ to have a blue edge. Thus, $\text{blue} \ \deg A=n-2$. Let $B$ be the only friend of $A$. Note that $B$ must be friend with all vertices since there exists a blue edge between $A$ and $v_i\in G-\{A,B\}$. If $G-\{B\}$ has $k$ edges, then answer is at most $\binom{n-1}{2}-k\leq \binom{n-1}{2}$ because $B$ has no blue edge which completes our proof as desired.$\blacksquare$