Let $n$ be an even positive integer, and let $G$ be an $n$-vertex graph with exactly $\tfrac{n^2}{4}$ edges, where there are no loops or multiple edges (each unordered pair of distinct vertices is joined by either 0 or 1 edge). An unordered pair of distinct vertices $\{x,y\}$ is said to be amicable if they have a common neighbor (there is a vertex $z$ such that $xz$ and $yz$ are both edges). Prove that $G$ has at least $2\textstyle\binom{n/2}{2}$ pairs of vertices which are amicable. Zoltán Füredi (suggested by Po-Shen Loh)
Problem
Source: USA December TST for IMO 2014, Problem 3
Tags: induction, inequalities, combinatorics proposed, combinatorics, graph theory, Extremal combinatorics
math154
24.12.2013 09:14
Here are hints for the solutions I have seen.
Keep the equality case in mind. Induction on $V$ or $E$...
Hint for 1with the stronger hypothesis of $\ge E-V/2$ amicable pairs.
Another Hint for 1One way to do this is by choosing an arbitrary edge $uv$ and removing $u,v$ as well as the edges incident to $u,v$. (One can equivalently work with a maximal, but not necessarily maximum, matching.)
There is also a slightly messier induction removing a well-chosen vertex instead, which gradually reduces the strengthened problem to regular bipartite graphs.
Keep the equality case in mind. Some kind of algebraic summation over amicable pairs, using a suitable "weighting".
Try modifying the summation involved in the classical problem of counting the number of amicable triples, or more precisely, triples $\{x,y,z\}$ such that $xz$ and $yz$ are both edges.
Hint for 2One may be tempted to directly use the inequality $\min(d(x),d(y)) \ge \sum_{z\in N(x)\cap N(y)} 1$, where $N$ denotes the neighborhood set and $d$ denotes degree. If we sum this over all vertices $z$, the RHS is easy to count (this is the double-counting argument in the classical problem), but we cannot easily relate the LHS to the number of amicable pairs.
However, we can modify the inequality...
Another Hint for 2Either of the following two inequalities suffices:
\[1 \ge \sum_{z\in N(x)\cap N(y)} \frac{d(x)^{-1} + d(y)^{-1}}{2}\]or the weaker inequality
\[1 \ge \sum_{z\in N(x)\cap N(y)} d(x)^{-1/2} d(y)^{-1/2}. \]
(Note that in each case, we get the number of amicable pairs on the LHS when we sum over all amicable pairs.)
Rephrase the number of amicable pairs $A$ in terms of...
Hint for 3the second neighborhood sets $N^2(v)$.
How can we lower bound $|N^2(v)|$? Keep the equality case in mind.
Another Hint for 3If $S$ denotes the set of nonzero-degree vertices, then $2A+|S| = \sum_{v\in G}|N^2(v)|$, so it suffices to show that $\sum_{v\in S} |N^2(v)| \ge \sum_{v\in S} |N(v)|$.
We can lower bound $|N^2(v)|$ by $\max_{u\in N(v)} |N(u)|$.
Edit: This is a special case of Lemma 2.1 in this paper.
colinhy
29.12.2013 02:55
Here's a nice solution I came up with - it's essentially knowing how to count things, counting in two ways, and Hall's marriage theorem.
We'll first rephrase the question statement (to make the numbers nicer) into $2n$ people with $n^2$ edges. We then wish to prove that there exists at least $n(n-1)$ amicable pairs.
Now, we count the number of amicable pairs each vertex is in. Obviously, the result will be twice the total number of amicable pairs. Note that for any vertex, the number of amicable pairs it is at least one less than the maximum degree among any of its neighboring vertices. Letting $i_{max}$ be the maximum degree among the vertices neighboring vertex $i$, we get that $N = \frac{1}{2}\sum_{i \in G} (i_{max} - 1) = \frac{1}{2}\sum_{i \in G} i_{max} - n$. Now, we present a lemma:
Lemma 1: For any graph $G$, we have that $\sum_{i \in G} i_{max} \ge \sum_{i \in G} d_i$, where $i_{max}$ is the maximum degree among the vertices neighboring vertex $i$ and $d_i$ is the degree of vertex $i$.
Proof: Consider the set of all vertices $S$ such that for any $i \in S$, $d_i > i_{max}$. We create a grid where each row corresponds to a vertex in $S$ and each column corresponds to a vertex not in $S$. We mark a cell if the corresponding vertices to its row and column are connected by an edge. Note that for any marked cell, there are more marked cells in its row than in its column (definition of vertices in $S$).
For each marked cell $k$ with $k_r$ marked cells in the same row as it (including itself), we assign a value equal to $\frac{1}{k_r}$. Thus, the sum of the marked cells in any row is equal to 1 and the sum of the marked cells in any column is less than 1. Taking any subset $s$ of $S$, the sum of all the marked cells in the corresponding rows is $|s|$. This implies that there are more than $|s|$ columns that have a marked cell in these rows. This satisfies the criteria for Hall's Marriage Theorem, so we can choose $|S|$ marked cells such that each vertex $i \in S$ is paired with a unique vertex $j \notin S$. Then, $i_{max} + j_{max} \ge d_i + d_j$ for every such pair of vertices $i, j$. For every vertex $v$ not paired up, it is not in $S$, so $v_{max} \ge d_v$. Summing all pairs and all vertices not in a pair, we get $\sum_{i \in G} i_{max} \ge \sum_{i \in G} d_i$.
Then, $N = \frac{1}{2}\sum_{i \in G} i_{max} - n \ge \frac{1}{2}\sum_{i \in G} d_i - n = \frac{1}{2}2n^2 - n = n(n-1)$, as desired.
numbertheorist17
30.12.2013 14:54
Does this not work?
Since there are no loops in $G$, there is no triangle. Therefore, by Mantel's Theorem, $G$ contains atmost $\frac{n^2}{4}$ edges. But since $G$ contains exactly $\frac{n^2}{4}$ edges, equality must be acheived, which is when $G$ is bipartite with each part containing $\frac{n}{2}$ verticies. But then, $G$ contains exactly $ 2\textstyle\binom{n/2}{2} $ amicable pairs, which doesn't seem right due to the wording of the problem.
Look here for Mantel's Theorem: https://www.dpmms.cam.ac.uk/~dc340/EGT1.pdf
mavropnevma
30.12.2013 15:08
numbertheorist17 wrote: Since there are no loops in $G$, there is no triangle. Why that? What you have proved is that if $G$ is triangle-free, thus complete bipartite, there are exactly that bounding number of amicable pairs, and that's all - a very particular case. Maybe, one could extract a solution by proving this is the extremal case (a graph $G$ with triangle(s) contains more amicable pairs than a triangle-free one). I think you interpreted "no loops" as being "no cycles"; but that is clearly wrong, since $G$ cannot be acyclic, having $n^2/4 > n-1$ edges for $n>2$. The complete bipartite model you have used has tons of even-length cycles.
JuanOrtiz
08.01.2014 21:00
In the definition of amicable, can $z=x$ or $z=y$. That is, if two vertices are joined by an edge, are they necessarily amicable?
math154
08.01.2014 21:06
JuanOrtiz wrote: In the definition of amicable, can $z=x$ or $z=y$. No, since $xx$ and $yy$ are not edges.
JuanOrtiz
12.01.2014 22:06
If $S$ is a set of vertices of the graph, we call $N(S)$ the set of points that are adjacent to at least one point in $S$. If $S$ is empty, then so is $N(S)$. For convenience, assume the cardinality of the empty set is $0$. For convenience, if $V$ is a vertex, we call $N(V)$ the set of vertices that are adjacent to $V$. (So as to avoid writing $N(\{V\})$.) Also for convenience, I will call the amicable pairs, "special" pairs. Also for convenience, I call $m=\frac{n}{2}$.
Now it is easy to see that a single vertex $Y$ belongs to $|N(N(Y))|-1$ special pairs. Therefore it is sufficient to prove that
$\sum |N(N(V))| \ge 2m^2$
where the sum runs over all vertices $V$. Now, call $f(V)$ the vertex adjacent to $V$ with degree $max_{X \in N(V)} d(X)$, where $d(X)$ denotes the degree of vertex $X$. If there are multiple vertices adjacent to $V$ with that degree, choose anyone of them and call that vertex $f(V)$. Clearly $|N(N(V))| \ge d(f(V))$. Therefore it is sufficient to prove
(1) $\sum ( d(f(V))-d(V) ) \ge 0$
where the sum runs over all vertices $V$, since the sum of all degrees is $2m^2$. Although it seems pretty intuitive, I couldn't find a quick way to prove this, and I don't think it's that easy.
Perhaps this is easier than the way I did itNow, we call a vertex $X$ a "BIG" vertex if $d(X) \textgreater d(f(X))$. If a vertex does not satisfy that inequality, we call it a "small" vertex. Clearly, if all vertices were small, we would be done. But this is not the case.
So we re-arrange the graph $G$ to create a bi-partite graph $H$. To do this, we erase all edges between small vertices. It is clear by the definition of BIG and small that no edges can exist between two big vertices. Therefore, the resulting graph is bi-partite, with the "big" edges in one side and the "small" vertices in the other. Now, we call $d(V)$ the degree of $V$ in $G$, and $h(V)$ the degree of $V$ in $H$: Since we only erased edges between small vertices, the inequality $h(X) \textgreater h(f(X))$ is true for big vertices and false for small vertices. Notice $h(X)=g(X)$ for big vertices.
Now, suppose that we could "marry" the big vertices. That is, assign each big vertex a small vertex that is adjacent to it, such that no small vertex is assigned twice. Say the married couples are $(B_1, s_1)$, ..., $(B_p, s_p)$, where $s_i$ is the small vertex that was assigned to $B_i$, and there are no more big vertices left unmarried. Call $M=\{B_1,...,B_p,s_1,...,s_p\}$ (married) and call $S$ the set of all vertices not in $M$. Notice all vertices in $S$ are small. Then we clearly have $d(f(s_i)) - d(s_i) + d(f(b_i)) - f(b_i) \ge d(b_i) - d(s_i) + d(s_i) - d(b_i) = 0$. So, in (1),
(2) $\sum ( d(f(V))-d(V) ) = \sum_{X \in M} ( d(f(X))-d(X) ) + \sum_{X \in S} ( d(f(X))-d(X) ) \ge 0$
since $d(X) \le d(f(X))$ for small vertices $X$.
Therefore, we need to prove that we can marry the big vertices in $H$. We will do this using Hall's theorem. Assume, by contradiction, that the vertices of $H$ cannot be married. Then by Hall's theorem, there exists a set $S$ of big vertices such that $|N(S)| \textless |S|$. Call the subgraph of $H$ induced by $S$, $\Omega$.
Now we will forget everything about the problem (we forget all the previous notation) and focus only in the existence of $\Omega$. It is a bi-partite graph. Some of its vertices are big, and the others are small. There are more big vertices than small vertices. There are no edges between two vertices of the same size. And $d(Y) \textgreater d(Z)$ if $Y$ is big and $Z$ is adjacent to it. If we prove that $\Omega$ cannot exist, we will have finished the problem.
To do this, assume such $\Omega$ does exist, and take $\Omega_1$ that satisfies the conditions with a minimal amount of vertices. Say $\Omega_1$ has $q$ edges. Suppose we could marry the small vertices in $\Omega_1$ (except those with degree $0$, we forget about those), and that the married couples are $(B_1, s_1), ..., (B_r, s_r)$, and there are no more small vertices remaining, but the big vertices $B_{r+1}, ..., B_t$ are left unmarried. Then
$\sum_{i=1}^r d(B_i) \textgreater \sum_{i=1}^r d(s_i) = q = \sum_{i=1}^t d(B_i) \ge \sum_{i=1}^r d(B_i)$,
which is impossible. Therefore, the small vertices (with positive degree) cannot be married, and, by Hall's theorem, there exists a set $T$ of small vertices such that $|N(T)| \textless |T|$. Call $\Omega_2$ the subgraph of $\Omega_1$ induced by $T$. Suppose we could marry the big vertices in $\Omega_2$. Then we could erase all these big vertices and their spouses from $\Omega_1$, and obtain a graph that satisfies the properties of $\Omega$ but that has less vertices than $\Omega_1$ (since the vertices in $T$ have a positive degree). This contradicts the minimality of $\Omega_1$.
Therefore, the big vertices in $\Omega_2$ cannot be married. So there exists a set $P$ of big vertices in $\Omega_2$ such that $|N(P)| \textless |P|$. Then we take the subgraph of $\Omega_2$ induced by $P$ and easily observe that it contradicts $\Omega_1$'s minimality.
So we're done.
add the number of amicable pairs each vertex is in, then use Hall on the big-small bipartite graphs.
another solution. It calls $T(X,Y)$ the number of common neighbors two vertices $X$ and $Y$ have. Clearly $\sum T(X,Y) = \sum {{d(V)}\choose{2}}$ but also $\sum \frac{T(X,Y)}{\sqrt{d(X)d(Y)}} \le A$ where $A$ is the number of special pairs. I don't know the rest of the solution but I'm pretty sure it can be obtained using these ideas
math154
13.01.2014 18:35
JuanOrtiz wrote:
Therefore it is sufficient to prove
(1) $\sum ( d(f(V))-d(V) ) \ge 0$
where the sum runs over all vertices $V$, since the sum of all degrees is $2m^2$. Although it seems pretty intuitive, I couldn't find a quick way to prove this, and I don't think it's that easy.
If $N(v)$ are the neighbor sets, then $\max_{u\in N(v)} |N(u)| \ge \frac{1}{|N(v)|}\sum_{u\in N(v)} |N(u)|$. Now summing over all $v$ of nonzero degree, everything boils down to $\frac{|N(u)|}{|N(v)|}+\frac{|N(v)|}{|N(u)|} \ge 2$ for edges $uv$.
JuanOrtiz wrote:
another solution. It calls $T(X,Y)$ the number of common neighbors two vertices $X$ and $Y$ have. Clearly $\sum T(X,Y) = \sum {{d(V)}\choose{2}}$ but also $\sum \frac{T(X,Y)}{\sqrt{d(X)d(Y)}} \le A$ where $A$ is the number of special pairs. I don't know the rest of the solution but I'm pretty sure it can be obtained using these ideas
the same AM-GM technique above.
polya78
26.01.2014 18:25
colinhy, that's a terrific proof! (I wish I had thought of it.) But perhaps there is a simpler way to prove Lemma 1. Let $i_{avg}$ be the average degree among the vertices neighboring vertex i. For any edge $E$ connecting vertices $i,j$, let $f(E)=\frac{d_i}{d_j}+\frac{d_j}{d_i}$. We have $\sum_{E\in G}f(E) \ge \sum_{E\in G}2=\sum_{i\in G}d_i $. But by counting by vertex instead of edge, we also have $\sum_{i\in G}i_{avg} = \sum_{E\in G}f(E)$.
colinhy
20.02.2014 05:26
That's a much cleaner and better proof for lemma 1 - I was searching for one using double counting for a while but couldn't think of one (yours is really nice). Putting the two together basically kills the problem in two lines o.O
math90
11.06.2016 13:19
For any amicable pair $\{x,y\}$, let $T(x,y)$ be the number of common neighbors of $x,y$.
For any vertex $v$, let $N(v)$ be the set of neighbors of $v$. $d_v$ is the number of neighbors of $v$.
Let $A$ be the set of amicable pairs.
Observation: $T(x,y)\leq min\{d_x,d_y\}$
$\implies\frac{1}{T(x,y)}\geq\max\{\frac{1}{d_x},\frac{1}{d_y}\}\geq\frac{1}{2}\left(\frac{1}{d_x}+\frac{1}{d_y}\right)$
Hence:
$|A|=\sum_{d_v\geq2}\sum_{\{x,y\}\subseteq N(v)}\frac{1}{T(x,y)}\geq\frac{1}{2}\sum_{d_v\geq2}\sum_{\{x,y\}\subseteq N(v)}\left(\frac{1}{d_x}+\frac{1}{d_y}\right)=\frac{1}{2}\sum_{d_v\geq2}\sum_{x\in N(v)}\frac{d_v-1}{d_x}=\frac{1}{2}\sum_{d_v\geq1}\sum_{x\in N(v)}\frac{d_v-1}{d_x}=$
$=\frac{1}{2}\sum_{\{v,x\}\subseteq A}\left(\frac{d_v-1}{d_x}+\frac{d_x-1}{d_v}\right)\geq\frac{1}{2}\sum_{\{v,x\}\subseteq A}\left(2-\frac{1}{d_x}-\frac{1}{d_v}\right)=\frac{1}{2}\left(2\cdot\frac{n^2}{4}-\sum_{d_v\geq1}\sum_{x\in N(v)}\frac{1}{d_v}\right)=$
$=\frac{n^2}{4}-\frac{1}{2}\sum_{d_v\geq1}1\geq\frac{n^2}{4}-\frac{n}{2}=\frac{n(n-2)}{4}=2\binom{n/2}{2}$
v_Enhance
26.09.2017 01:36
colinhy wrote: That's a much cleaner and better proof for lemma 1 - I was searching for one using double counting for a while but couldn't think of one (yours is really nice). Putting the two together basically kills the problem in two lines o.O I should point out that Lemma 1 is by no means new. If you spend enough time on Facebook, you might have even seen pop articles about it: on average your friends are more popular than you. (Or more boringly, the friendship paradox.) To be self-contained, the relevant claims are: Lemma: [On average, your friends are more popular than you] For a vertex $v$, let $a(v)$ denote the average degree of the neighbors of $v$ (setting $a(v) = 0$ if $\deg v = 0$). Then \[ \sum_v a(v) \ge \sum_v \deg v = 2 \# E. \] Proof. Ignoring isolated vertices, we can write \begin{align*} \sum_v a(v) &= \sum_v \frac{\sum_{w \sim v} \deg w}{\deg v} \\ &= \sum_{v} \sum_{w \sim v} \frac{\deg w}{\deg v} \\ &= \sum_{\text{edges } vw} \left( \frac{\deg w}{\deg v} + \frac{\deg v}{\deg w} \right) \\ &\overset{\text{AM-GM}}{\ge} \sum_{\text{edges } vw} 2 = 2\#E = \sum_{v} \deg v \end{align*}as desired. $\blacksquare$ Corollary: [On average, your most popular friend is more popular than you] For a vertex $v$, let $m(v)$ denote the maximum degree of the neighbors of $v$ (setting $m(v) = 0$ if $\deg v = 0$). Then \[ \sum_v m(v) \ge \sum_v \deg v = 2 \# E. \] All this is agnostic to the graph $G$, and then the problem dies upon realizing the number of amicable pairs is at least $\frac12 \sum_v (m(v)-1)$.
rafayaashary1
26.09.2017 04:21
v_Enhance wrote: If you spend enough time on Facebook, you might have even seen pop articles about it There goes my motivation
Taha1381
12.08.2018 14:57
math154 wrote: Here are hints for the solutions I have seen.
Keep the equality case in mind. Induction on $V$ or $E$...
Hint for 1with the stronger hypothesis of $\ge E-V/2$ amicable pairs.
Another Hint for 1One way to do this is by choosing an arbitrary edge $uv$ and removing $u,v$ as well as the edges incident to $u,v$. (One can equivalently work with a maximal, but not necessarily maximum, matching.)
There is also a slightly messier induction removing a well-chosen vertex instead, which gradually reduces the strengthened problem to regular bipartite graphs.
There is a similar problem which uses the same idea unfortunatly I don't know the source but I think it is well-known. If you replace the last $n$ with $1$ it is just Tooran's theorem. Problem:Let $G$ be a graph with $2n$ vertices and $n^2+1$ edges show that $G$ has at least $n$ triangles.
v_Enhance
12.08.2018 19:18
Quote: Problem:Let $G$ be a graph with $2n$ vertices and $n^2+1$ edges show that $G$ has at least $n$ triangles. The theorem you're referring to is called Turan-Rademacher in the literature I think (see e.g. https://projecteuclid.org/download/pdf_1/euclid.ijm/1255631811 ).
K_Mirrorheart
30.12.2018 12:17
I've looked through the posts and thought this is a new idea.(Perhaps I'm wrong.) The proof is stated below.
Instead of proving the original proposal, we prove a more general result: any $n$-vertex graph $G$ contains at most $\frac{n}{2}$ more edges than amicable pairs.
Define a function $F(G)$ to be the difference between the number of edges in $G$ and the amicable pairs in $G$. Since there are only $2^{\frac{n(n-1)}{2}}$ choices for $G$, there must exist several cases of $G$ for $F$ to attain its maximal value and we select a graph $G_1$ in these cases to have minimal edges. For any vertex $A_1$, suppose $\deg A_1=k$ and its neighbors are $B_1$ to $B_k$. Now we delete the $k$ edges $A_1B_i$, where $1\le i\le k$. By the minimality of $G_1$, we delete at most $k-1$ amicable pairs. However, it's easy to see that all amicable pairs containing $A_1$ are deleted, and there are at least $\max_{1\le i\le k}(\deg B_i)-1$ such pairs. So we obtain the inequality that if vertices $A$ and $B$ are connected, then $\deg A \le \deg B$, and, analogously, $\deg B \le \deg A$. This means that all connected components of $G_1$ are regular.
Select a regular subgraph $S_1'$ with $u_1$ vertices and the degree of each vertex being $r_1$. Call $(A,B,C)$ a good triple if $A$ and $C$ are both neighbours of $B$(do not distinguish A and C).By summing up in $B$, the number of good triples is $u_1\binom{r_1}{2}$. Then, every amicable pair contributes to at most $r_1$ good triples, so there are at least $\dfrac{u_1\binom{r_1}{2}}{r_1}=\frac{u_1(r_1-1)}{2}$ amicable pairs in $S_1'$ i.e. $F(S_1')\le\frac{u_1r_1}{2}-\frac{u_1(r_1-1)}{2}=\frac{u_1}{2}$.
Obviously, $F(G_1)=\sum_iF(S_i')\le\sum_i\frac{u_i}{2}=\frac{n}{2}$
as desired.
My English and Latex skills are poor, so point out incorrect usages if possible.
AnonymousBunny
21.04.2019 20:22
This looks significantly different from the other posts, can someone please verify its correctness?
Rephrase the problem as follows: given a $2n$ vertex graph with $n^2$ edges, show that it has at least $n(n-1)$ amicable pairs.
Since the sum of degrees is $2n^2$ there exists a vertex with degree $\leq n$, call it $r$. Consider a DFS spanning tree rooted at $r$ (so every other edge connects a vertex to one of its ancestors). Let $dep(v), par(v)$ be the depth and parent of $v$ in this tree respectiely. For every $(u,v) \in E$ with $u,v \neq r$ and $dep(u)>dep(v)$, consider the amicable pair $(u, par(v))$ (they share the common neighbor $v$). I claim the pairs obtained this way are distinct. Suppose we obtain the same pair $(u,v)$ from $(u_1, v_1)$ and $(u_2, v_2)$ and $dep(u_1)>dep(v_1), dep(u_2)>dep(v_2), dep(u)>dep(v)$. Then we must have $u_1=u_2=u$. But this also uniquely determines $v_i$: we have $par(v_i)=v$ and $v_i$ lies on the path from $r$ to $u$. There is exactly one such vertex: the child of $v$ whose subtree contains $u$. Thus $v_1=v_2$ and there is no overcounting. Since we chose the degree of $r$ to be $\leq n$, we get one such pair from each of the remaining atleast $n^2-n$ edges.
yayups
05.06.2019 23:40
Let $A$ be the answer. Note that the number of amicable pairs with $x$ is at least one less than the degree of any neighbor, so it's actually at least one less than the average degree of all it's neighbors. Thus, \[2A\ge\sum_{x\in V}\left(-1+\sum_{z\sim x}\frac{d_z}{d_x}\right),\]so \[2A\ge -n+\sum_{\{x,z\}\in E}\left(\frac{d_z}{d_x}+\frac{d_x}{d_z}\right),\]which by AM-GM is at least \[2A\ge -n+2\frac{n^2}{4}\implies A\ge \frac{n}{2}\left(\frac{n}{2}-1\right)=2\binom{n/2}{2},\]as desired.
TheUltimate123
24.03.2020 01:04
Solved with Th3Numb3rThr33. Let $G$ have $E=\tfrac{n^2}4$ edges. For each $v\in G$, Let $N(v)$ be the set of vertices adjacent to $v$, so that $|N(v)|=\deg v$. The pith of this problem is this infamous paradox: Lemma: [Friendship paradox: On average, your friends are more popular than you] If a vertex $v$ is chosen from $G$, then \[\mathbb E\left[\frac1{\deg v}\sum_{u\in N(v)}\deg u\right]\ge\mathbb E[\deg v],\]with equality if and only if the connected components of $G$ are regular. Proof. The proof is by taking the sum over all $v$: \[\sum_{v\in G}\frac1{\deg v}\sum_{u\in N(v)}\deg u=\sum_{uv\in E}\left(\frac{\deg u}{\deg v}+\frac{\deg v}{\deg u}\right)\ge 2E=\sum_{v\in G}\deg v.\]Equality holds if and only if $\deg u=\deg v$ for all edges $uv$. $\blacksquare$ We use a much weaker form of the lemma: on average, your most popular friend is more popular than you. This gives \[\sum_{v\in G}\left\lvert N^2(v)\right\rvert\ge\sum_{v\in G}\left(\max_{u\in N(v)}\deg u-1\right)\ge\sum_{v\in G}(\deg v-1)=2E-n=4\binom{n/2}2,\]and we are done.
srisainandan6
26.07.2021 19:29
Denote $N$ as our answer. It is easy to see that $2N \ge \sum_{v \in V} (\max{d(n) - 1)}$ where $\max(d(n))$ is the greatest degree of any neighbor of $v$. Since it is known that $\sum_{v \in V} \max(d(n)) \ge \sum_{v \in V} d(v)$ (On average, your most popular friend is more popular than you), we have that $2N \ge \sum_{v \in V} (\max{d(n) - 1)} \ge \sum_{v \in V} d(v) - n = \frac{n^2}{2} - n$. Dividing by $2$ we get the desired result. $\blacksquare$
SHZhang
05.09.2022 00:08
Consider the following algorithm that generates a partition $P$ of $V(G)$:
1. Let $S = V(G)$.
2. Take a subset $T$ of $S$, such that any two distinct elements $x, y \in T$ are not amicable and such that the size of $T$ is maximized. Add $T$ to the partition and set $S := S \setminus T$.
3. Repeat step 2 until $S$ is empty.
Let $P = \{S_1, S_2, ..., S_k\}$, where each $S_i$ is a set of the partition.
Claim: $\frac{n}{2} + \sum_{1 \le i < j \le k} \min(|S_i|, |S_j|) \ge \frac{n^2}{4}$.
Proof: We claim that the LHS is an upper bound on $|E(G)| = \frac{n^2}{4}$. Note that:
(1) For each $S_i$, there are at most $\frac{|S_i|}{2}$ edges internal to $S_i$; otherwise it would be possible to find an amicable pair inside $S_i$. Summing this bound over all $S_i$ gives an upper bound of $\frac{n}{2}$ edges whose endpoints are in the same $S_i$.
(2) For each unordered pair $\{S_i, S_j\}$, there are at most $\min(|S_i|, |S_j|)$ edges between $S_i$ and $S_j$. To prove that, assume WLOG $|S_i| \le |S_j|$. Then each edge between $S_i$ and $S_j$ must involve a different vertex in $S_i$, otherwise an amicable pair would be formed between two vertices of $S_j$. Therefore there are at most $|S_i|$ such edges, as desired. Summing this for each possible choice of $i$ and $j$ gives that there are at most $\sum_{1 \le i < j \le k} \min(|S_i|, |S_j|)$ edges whose endpoints are in different sets of $P$.
Adding these two bounds together gives the desired conclusion.
Corollary: $\sum_{1 \le i < j \le k} \min(|S_i|, |S_j|) \ge \frac{n^2}{4} - \frac{n}{2} = 2\binom{n/2}{2}$.
Now again consider an unordered pair $\{S_i, S_j\}$. Assume WLOG that $S_i$ was added to $P$ on an earlier iteration of the algorithm than $S_j$. Then, $|S_i| \ge |S_j|$; otherwise $S_j$ would have been strictly preferred to $S_i$ on the step of the algorithm where $S_i$ was chosen. Also, for each $u$ in $S_j$, there must exist $v$ in $S_i$ such that $\{u, v\}$ is amicable; otherwise, $S_i \cup \{u\}$ would have been strictly preferred to $S_i$ on the step $S_i$ was chosen. Therefore, there are at least $|S_j| = \min(|S_i|, |S_j|)$ amicable pairs involving one vertex from $S_i$ and another from $S_j$. Summing this over all possible unordered pairs $\{S_i, S_j\}$, we have $$A \ge \sum_{1 \le i < j \le k} \min(|S_i|, |S_j|),$$where A is the number of amicable pairs in the graph.
Combining this with the earlier corollary gives
$$A \ge \sum_{1 \le i < j \le k} \min(|S_i|, |S_j|) \ge 2\binom{n/2}{2},$$which is the desired conclusion.
HamstPan38825
14.09.2022 19:45
Lemma. [Friendship Lemma; mentioned before in this thread] Let $G$ be a graph. For all $V \in V(G)$, let $a(V)$ be the average degree of the neighbors of $V$. Then we must have $$\sum_{V \in V(G)} a(V) \geq 2|E(G)|.$$ Proof. Delete any isolated vertices; thus, we can assume that $d(V) > 0$. Then, $$\sum_{V \in V(G)} a(V) = \sum_{V \in V(G)} \frac 1{d(V)} \sum_{W \in N(V)} d(W).$$We can rewrite this double sum as $$\sum_{VW \in E(G)} \left(\frac{d(W)}{d(V)} + \frac{d(V)}{d(W)}\right) \geq 2|E(G)|$$by AM-GM. $\blacksquare$ We can rewrite the problem as showing that the sum of the number of unordered pairs containing a vertex $V$ over all $V$ is at least $2n(n-1)$. Call this quantity $n_V$; I claim that $$n_V \geq \max_{W \in N(V)} d(W) - 1.$$Notice that for any $Z \in N(W)$ for some $W \in N(V)$, $\{Z, V\}$ is a nice pair containing $V$. This means that every one of the $d(W)$ edges emanating from $W$ not containing $V$ must create a valid $n_V$. Thus, $n_V \geq a(V) - 1$ as the maximum must be greater than the average, so we have $$\sum_V n_V \geq \sum_V a(V) - 2n \geq 2n^2 - 2n = 2n(n-1)$$by the previous lemma.
Eyed
14.03.2023 20:25
I don't have friends, so I can't use the friendship lemma We will show the stronger statement: For even $n$, if graph $G$ has $\frac{n^2}{4} + a$ edges, then it has at least $\frac{n^2-2n}{4} + a$ amicable pairs. We will prove this with induction on $n$. Our base case of $n = 2$ is trivial: we have $a = 0$ or $a = -1$, both of which give $0\geq a$ amicable pairs. For our inductive hypothesis, assume the statement is true for $n-2$; we will show it for $n$. Let $G$ be a graph with $\frac{n^2}{4} + a$ edges and $n$ vertices. Consider some edge $AB\in G$, and let $\deg A + \deg B = x+2$. Then, $G\backslash A,B$ has $n-2$ vertices and $\frac{n^2}{4} + a - x = \frac{(n-2)^2}{4} + n-1 + a - x - 1$ edges. By our inductive hypothesis, there are $\frac{(n-2)(n-4)}{4} + n - 1 + a - x + 1 = \frac{n^2 - 2n}{4} + a-x$ amicable pairs in $G\backslash A,B$, or $\frac{n^2 - 2n}{4} + a-x$ amicable pairs in $G$ that do not include $A$ nor $B$. Now, for every vertex $C$ adjacent to $A$ such that $C\neq B$, we have $B,C$ is an amicable pair. Similarly, for every vertex $D$ adjacent to $B$ such that $D\neq A$, $D,A$ is an amicable pair. Since $A,B$ are adjacent and $\deg A + \deg B = x+2$, there are at least $x$ of such amicable pairs $(A,C$ or $(B,D)$. Thus, $G$ has at least $\frac{n^2 -2n}{4} + a$ amicable pairs, completing the induction. Plugging in $a = 0$ gives the desired result.
Inconsistent
19.06.2023 06:33
Isn't this just induction? I might be crazy. For ease of writing, let $m = \frac{n}{2}$. I claim that given a graph on $n$ vertices with at least $m^2$ edges, the number of edges minus the number of amicable pairs is at most $m$. We induct from $m$ to $m+1$. Base case is trivial. Now to induct up, assume the contrary is true on a graph for $m+1$. Then there must be more edges than amicable pairs, so choose an edge where the two vertices $u, v$ are not amicable. Then their neighbor sets must be mutually disjoint, so let them cover $k$ other vertices. Then since $v$ is amicable with all the neighbors of $u$ and $u$ is amicable with all the neighbors of $v$, the addition of $u, v$ to the graph with those two vertices removed adds at least new $k$ amicable pairs. Also note that it adds exactly $k+1$ edges. Now since $(m+1)^2 - (k+1) \geq (m+1)^2 - (2m-1) = m^2$, we can apply the inductive hypothesis, so the number of edges minus amicable pairs in the graph with $u, v$ removed is at most $m$. Then this readdition of $u, v$ adds at most one to the difference, so the new difference is at most $m+1$ as desired. Now just apply this to the problem, finishing immediately.
ChanandlerBong
13.07.2023 11:52
We will prove a stronger result. Claim: Suppose $G$ is a $2m-$vertex simple graph with $k$ edges, where $0\leq k\leq m^2$, then $G$ has at least $\text{max}\{0,k-m\}$ pairs of vertices which are amicable. We prove our claim by induction on $m$. The case $m=1,2$ is trivial. Now assume that the claims holds for $m-1$, where $m\geq 3$. Consider a graph $G=(V,E)$ with $|V|=2m$ and $|E|=k\leq m^2$. First notice that \begin{align*} &\frac{1}{k}\sum\limits_{\{u,v\}\in E}deg(u)+deg(v)\\ =&\frac{1}{k}\sum\limits_{v\in V}deg(v)^2 \\ \geq& \frac{1}{k}\cdot \frac{1}{2m}(\sum\limits_{v\in V}deg(v))^2 \\ =&\frac{2k}{m} \end{align*}Thus there exists an edge $uv$ of $G$, such that $t:=deg(u)+deg(v)\geq \frac{2k}{m}$. Set $G':=G-\{u,v\}$, we know that $G'$ has $2m-2$ vertices and $k-t+1$ edges. Since $k\leq m^2$, $G'$ has no more than $k\frac{m-2}{m}+1\leq (m-1)^2$ edges. Due to the inductive hypothesis, we conclude that $G'$ has at least $k-t-m+2$ pairs of vertices which are amicable. Observe that if $uw\in E$, then $\{v,w\}$ is amicable. Therefore there are at least $deg(u)-1+deg(v)-1=t-2$ amicable pairs in $G$ with one of the two vertices being either $u$ or $v$. In total, there are at least $(k-t-m+2)+(t-2)=k-m$ amicable pairs in $G$, completing our inductive step. Done!
IAmTheHazard
22.08.2023 19:51
what the heck Let $n=2m$. I will prove that in a simple $2m$-vertex graph with $e$ edges, there are at least $e-m$ amicable pairs. This is by induction on $m$, with the base case of $m=1$ being obvious. Now, if $m \geq 2$, pick any (!) edge $\overline{vw}$ in the graph and delete $v,w$ (as well as the edges adjacent to them). It is easy to see that at least $\deg v-1$ amicable pairs other than $\{v,w\}$ (if it is amicable) contain $w$, and likewise at least $\deg w-1$ amicable pairs other than $\{v,w\}$ contain $v$. Since a total of $\deg v+\deg w-1$ edges are deleted, it follows that the number of amicable pairs deleted is at least $1$ greater than the number of edges deleted, and since $m$ also decreases by $1$ we are done by hypothesis. $\blacksquare$ Remark: I find it mildly amusing that this thread contains 1. generalized inductive approaches for any number of edges, 2. generalized inductive approaches for at most $m^2$ edges, and 3. generalized inductive approaches for at least $m^2$ edges
KevinYang2.71
18.05.2024 03:50
trivel We claim that any graph $G$ has at least $||G||-\frac{1}{2}|G|$ amicable pairs. We proceed by induction on $||G||$ with the base case trivial. Let $G$ be a graph and assume the statement for smaller $||G||$. Trivially assume there exists an edge $vu\in E(G)$. Then any $w\in N(v)\setminus\{u\}$ is amicable with $u$ and any $w\in N(u)\setminus\{v\}$ is amicable with $v$. Thus there are at least $d(v)+d(u)-2$ amicable pairs containing $v$ or $u$. By the induction hypothesis, $G$ has at least \[ ||G-\{v,u\}||-\frac{1}{2}|G-\{v,u\}|+d(v)+d(u)-2=||G||-d(v)-d(u)+1-\frac{1}{2}|G|+1+d(v)+d(u)-2=||G||-\frac{1}{2}|G| \]amicable pairs, as desired. $\square$
dolphinday
30.07.2024 00:36
Let $N(v)$ be the neighborhood of vertices for some vertex $v \in G$, and let $d(v)$ be the degree of vertex $v$. Then we will prove the following lemma; \[\mathbb{E}_{x \in G} \left [\frac{1}{d(x)} \left( \sum_{y \in N(x)} d(y) \right )\right] \geq 2E\]We first note that \[\sum_{x \in G} \frac{1}{d(x)} \left( \sum_{y \in N(x)} d(y) \right ) = \sum_{\overline{xy} \in G} \frac{d(x)}{d(y)} + \frac{d(y)}{d(x)} \geq 2\]where the last $\geq$ is implied by AM-GM. Then, summing over all edges $\overline{xy}$ gives us $2 \cdot E$ as desired. Now note that the number of amicable pairs containing some vertex $x$ is at least $d(y) - 1$ for some $y \in N(x)$. Taking the $y$ with $d(y)$ maximal over all $x$, and summing $d(y)$ gives us \[\sum_{x \in G} d(y) - 1 \geq 2E - n\]from our lemma. Then $2E - n = \frac{n^2}{2} - n \geq 2\binom{\frac{n}{2}}{2}$ as desired.
N3bula
23.10.2024 12:45
I will prove by induction that if a graph has $E$ edges and $V$ vertices that it has at least $\frac{2E+V}{2}$ amicable pairs. Suppose that for all graphs on $m<n$ vertices they have at least $\frac{2E+V}{2}$ pairs. Clearly the result holds if the graph is disconnected, now WLOG the graph is connected, clearly if the graph is not regular there exists two connected vertices of different degree, now call those vertices $x$ and $y$ and WLOG $d(x)>d(y)$, now from the induction we get that for the graph excluding $y$ that there are $\frac{2E+V}{2}$ pairs, and we have that $y$ is in at least $d(y)$ distinct pairs, which suffices. For a regular graph, if it has an even number of vertices the induct works as is because the inequality with $\frac{2E+V}{2}$ relating to the number of pairs is strict, and when the number of vertices is even we can remove another vertice which has a smaller degree than a neighboring vertice and we get the inequality become strict again so it works.