In graph theoretic terms: we wish to determine the maximum possible value of \[ S(G) \overset{\text{def}}{=} \sum_{e = vw} \min \left( \deg v, \deg w \right) \]across all graphs $G$ with $2017$ edges. We claim the answer is $63 \cdot \binom{64}{2} + 1 = 127009$. The two solutions are hidden for length.

Remark: Interestingly, the graph $C_4$ has $\binom 32+1 = 4$ edges and $S(C_4) = 8$, while $S(L_3) = 7$. This boundary case is visible in the combinatorial solution in the base case of the first claim. It also explains why we end up with the bound $S(G) \le 127010$ in the second algebraic solution, and why it is necessary to analyze the equality cases so carefully; observe in $k=3$ the situation $d_1 = d_2 = d_3 = d_4 = 2$. Remark: The quantity \[ S(G) = \sum_{e = vw} \min \left( \deg v, \deg w \right). \]in the problem has an interpretation: it can be used to provide to use it to provide a bound on the number of triangles in a graph $G$. To be precise, $\# E(G) \le \frac 13 S(G)$, since an edge $e = vw$ is part of at most $\min(\deg v, \deg w)$ triangles.

@v_Enhance: How did you create this problem?

He's a special person!

mickeydomath wrote: @v_Enhance: How did you create this problem? I came up with the quantity $S(G)$ in a failed attempt to provide a bound on the number of triangles in a graph, since this is natural to consider when you do a standard double-counting via the edges of the triangle. I think the problem was actually APMO 1989, and I ended up not solving the problem (the solution is much simpler), but the quantity $S(G)$ stuck in my head for a while after that. Later on that month I was keeping Danielle company while she was working on art project (flower necklace), and with not much to do except doodle on tables I began thinking about $S(G)$ again. I did have the sense that $S(G)$ should be maximized at a graph close to a complete graph. But to my frustration I could not prove it for a long time. Finally after many hours of trying various approaches I was able to at least show that $S(G)$ was maximized for complete graphs if the number of edges was a triangular number. I had come up with this in March 2016, which would have been perfect since $2016$ is a triangular number, but it was too late to submit it to any contest (the USAMO and IMO deadlines were long past). So on December 31, 2016 I finally sat down and solved it for the case $2017$, which took another few hours of thought, then submitted it to that year's IMO. To my dismay it was rejected, but I passed it along to the USA TST after that, thus making it just in time for the close of the calendar year.

Let $S(n)$ be the maximum value of $ \sum_{e = dv} min(deg(d), deg(v)) $, ranging over all graphs with $n$ edges. Is it true that in general $$S(n) = \binom{k}{2}(k-1) + (n - \binom{k}{2})^2 + \binom{n-\binom{k}{2}}{2}$$, where $$k = \displaystyle \lfloor \frac{1}{2} + \sqrt{\frac{1}{4} + 2n} \rfloor $$, say for all $n > 10^{10^{10}}$ ?

, but the other way looks difficult)

Congratulate for such a great problem and impressive solution, Evan!

By the way I think this problem can be generalized to $\binom{k}{2}+c$ where $c$ is a constant for $k$ sufficient large, but rather difficult.

The problem is solved for all numbers of edges here by Ashwin Sah and Mehtaab Sawhney. In addition, the authors tackle the same question for bipartite graphs, forests, and planar graphs.

Oh thank you for advertising this paper by me and Ashwin. The key idea for all graphs is that there is Lemma 9/10 and 14/15. Note that 9/10 are essentially extension/versions of the combinatorial solution in vEnhance's post. (These lead to a non-inductive version of vEnhance's solution that are arguably simpler.) Then 14/15 handle the case where we don't have a universal vertex, this is essentially the trickiest thing in the paper and once one understands this the problem is quite easy.

Is this problem related to https://artofproblemsolving.com/community/u162946h1500991p8853725 ?

Mosquitall wrote: Is this problem related to https://artofproblemsolving.com/community/u162946h1500991p8853725 ? Obviously no since it submits an extremely trivial & weak upper bound !

v_Enhance wrote: In graph theoretic terms: we wish to determine the maximum possible value of \[ S(G) \overset{\text{def}}{=} \sum_{e = vw} \min \left( \deg v, \deg w \right) \]across all graphs $G$ with $2017$ edges. We claim the answer is $63 \cdot \binom{64}{2} + 1 = 127009$. The two solutions are hidden for length.

Remark: Interestingly, the graph $C_4$ has $\binom 32+1 = 4$ edges and $S(C_4) = 8$, while $S(L_3) = 7$. This boundary case is visible in the combinatorial solution in the base case of the first claim. It also explains why we end up with the bound $S(G) \le 127010$ in the second algebraic solution, and why it is necessary to analyze the equality cases so carefully; observe in $k=3$ the situation $d_1 = d_2 = d_3 = d_4 = 2$. Remark: The quantity \[ S(G) = \sum_{e = vw} \min \left( \deg v, \deg w \right). \]in the problem has an interpretation: it can be used to provide to use it to provide a bound on the number of triangles in a graph $G$. To be precise, $\# E(G) \le \frac 13 S(G)$, since an edge $e = vw$ is part of at most $\min(\deg v, \deg w)$ triangles. Why is sum of $a_i$ 4034 in the algebraic solution?

Typo. Should be $\sum_i a_i = 2017$. Thanks.

Let $F(G)$ be the sum of $\min \left( \deg v, \deg w \right)$ over edges $\overline{vw}$. Since type of $G$ with $n(n+1)/2+1$ edges are finite, the maximal case exists for $F$. Considering explicit example, graph with $(n+1)$-clique, we know the maximum is at least $n^2(n+1)/ 2 + 1$. To get contradiction, assume the maximum is bigger than $n^2(n+1)/ 2 + 1$. Case1 : There exists a maximal graph with no vertex with full-degree. Claim There exists a maximal graph with $n+2$ vertices. Assume, $G$ is the maximal graph with minimum number of vertices $>n+2$. Select any vertex $p$ with minimal degree $a$. We will delete $p$ and $a$ edges connected and create new $a$ edges so that the sum does not decrease. First, add at most $a$ edges to make non-full degree neighbor to get back their original degree. Next, place remaining edges anywhere. Then there are no points with decreased degree and new edges has larger number than before. Therefore, assume there are $n+2$ vertices. Let $q$ has the minimal degree $\beta$ which is at least $\alpha$. If all the edges has contribution of at most $n$, the sum should is at most $n(E-\beta)+\beta^2$. Compare to $n^2(n+1)/ 2 + 1$, the only possible case is when $\beta = n$. However, if every vertex has degree $n$, the number of edge does not fits except for one case $n=2$. Case2 : There exists a vertex $p$ with maximal degree. We will remove the point $p$ and edges connected to $p$. Denote this graph by $G^\prime$. Remaining edges are at most $n(n+1)/2-1-\deg p$ and the value for each edge decrease exactly 1. Numbers on removed edge between $p$ and $v$ was always $\deg v$. Therefore, $F(G) = F(G^\prime)+\sum _{v\ne p} \deg v + E^\prime$$=F(G^\prime)+3 n(n+1)/2 + 3 - 2\deg p$ . By comments below, $F(G^\prime)$ is less than $n(n-1)^2 /2$ and we get $F(G)$ is at most $n^2(n+1)/ 2 + 1$. Therefore, there are no such case with $F(G)$ greater than $n^2(n+1)/ 2 + 1$ except for $n=2$. When $n=2$, as v_Enhance wrote above, 4-cycle gives the maximum. For number of edge = $n(n+1)/2$ Same steps, but easier. Use induction. Case2 is automatically done. This time just $\deg p$ can be $n$. Also for the case1, we can always reduce the number of points until there are only $n+1$ vertices. Thus, $F(G)$ is at most $n^2(n+1)/2$ for the case.

I thought my proof can give full generalization but Case1 is hard to handle for the other number of edges.

To give a example for the result 127009. There are 64 different entrees for 2016 mathematicins. 64.63/2 = 2016 so all these mathematicians' entrees bill is 63. Cause all entrees ordered exactly 63 times from this 64 for entrees. That makes the cash for these 2016 people 127008 (63x2016) . And for the 20017Th person we give two entrees which is different from the 64 entrees above. So for the 2017th people we have to give 1cash. Cause it has two unique entress. From 127008+1 = 127009. Give's the desired example for the reesult.

Pretty similar to this 239 MO problem. https://artofproblemsolving.com/community/c6h2225198p16947197

Take the graph theory interpretation where each vertex represents a dish and each edge represents a person buying the dish. The answer is $\binom n2 (n-1)+1$. Let the value of an edge $uv$ be $\min(\deg(u), \deg(v))$. The construction is $K_n$ plus an edge, which has $\binom n2$ edges with value $n-1$ and one vertex with weight 1. Sort the degrees $d_1\ge d_2\ge \cdots \ge d_k$ and the vertices $v_1, v_2, \cdots, v_k$. Define the \textbf{priority} of an edge $v_iv_j$ to be $\max\{i,j\}$. Note there exists at most $t-1$ edges with weight $t$. Therefore, the answer is at most $$f(G)=d_2+2d_3+\cdots+(n-1)d_n+d_{n+1}$$ We focus on the degree sequence for now. I will show that if this value exceed $\binom n2 (n-1)+1$, either the graph doesn't exist or the actual $$\sum_{uv \text{ edge }} \min \{ \deg(u),\deg(v)\}$$is at most $\binom n2 (n-1)+1$ First, this value is at most $$ \frac n2 (d_2+d_3+\cdots+d_n)+d_{n+1}$$ By handshaking lemma, $\sum d_i=n(n-1)+2$. If $d_2+\cdots+d_n> (n-1)^2$, then $d_1\ge n$, so adding them up gives $d_1+\cdots+d_n\ge n(n-1)+2$, which implies all other vertices have 0 degree, so the graph is a subgraph of $K_n$, but that means the number of edges is at most $\binom n2$. Therefore, $d_2+\cdots+d_n\le (n-1)^2$. Let their sum be $S$. We casework on the size of $d_1$. Case 1: $d_1=n-1$. Subject to $S+d_{n+1}=n(n-1)+2-(n-1)=(n-1)^2+2$ and $S\le (n-1)d_1$, we should maximize $S$ and get $S=(n-1)^2, d_{n+1}=2$. This is impossible because this means only $d_1,\cdots,d_{n+1}$ are nonzero degrees, so the graph is a $K_n$ minus an edge $uv$ but add edges $uk, vk$ where $k$ is not in the clique. The sum of $\min\{ \deg u, \deg v\}$ over all edges is less than $1+n(n-1)^2/2$ Case 2: $d_1\ge n$ then $S+d_{n+1}\le n(n-1)+2-n=(n-1)^2+1$. To beat the sum of $1+(n-1)\binom n2$, we need $S>(n-1)^2$ and $d_{n+1}=0$ and $d_1=n$, since the claimed bound is achieved at $d_1=n, S=(n-1)^2, d_{n+1}=1$ This means there are more than $\binom n2$ edges but only $n$ vertices of nonzero degree, impossible! If $d_1\ge n+1$ then $S+d_{n+1} \le (n-1)^2$, so $\frac n2 S +d_{n+1}\le (n-1)\binom n2$

Restate the problem in terms of an undirected graph where each entree is a vertex and each mathematician is an edge. Then define the score of a graph, $s(G)$, as the sum of $\min(\text{deg }u, \text{deg }v)$ over all edges $(u, v)$. Define $f(m)$ as the maximum possible score of a graph with $m$ edges; we want to find $f(2017)$. Call a vertex $v$ of a graph $G$ dominant if $v$ is connected to all other vertices of $G$. Lemma 1: Suppose a graph $G$ has $n$ vertices and $m$ edges, with $m \le \frac{(n-1)(n-2)}{2}$, and no dominant vertex. Then there is a graph $G'$ with $n-1$ vertices and $m$ edges such that $s(G') \ge s(G)$. Proof: Let $v$ be a vertex of $G$ with minimum degree. Let $u_1, \dots, u_k$ be the vertices adjacent to $v$, where $k$ is the degree of $v$. To produce $G'$, we modify $G$ by first deleting $v$, then adding back $k$ edges such that for each $u_i$, there is at least one added edge having $u_i$ as an endpoint. Since no $u_i$ was dominant in $G$, for each $u_i$ there is at least one edge we could add; the condition $m \le \frac{(n-1)(n-2)}{2}$ also ensures that there are enough missing edges for us to add $k$ edges. So we can repeatedly choose a $u_i$ that has no added edge yet, and add an edge adjacent to it; this will happen at most $k$ times before all $u_i$ are satisfied, after which we can add arbitrary edges. We now show $s(G') \ge s(G)$. To do that, we note that the degree of each non-deleted vertex did not decrease, so the contribution of each non-changed edge to $s(G')$ did not decrease. The contribution of each changed edge went from $k$, the minimum degree of $G$, to the minimum of two degrees that are not lower than $k$, so this part of $s(G')$ did not decrease either compared to $s(G)$. $\square$ Lemma 2: Suppose a graph $G$ has $n$ vertices, $m$ edges, and a vertex $v$ with degree $k$. Then $s(G) \le f(m-k) + 3m - 2k$. Proof: Let $E_1$ be the set of edges adjacent to $v$, and $E_2 = E(G) \setminus E_1$. Then $|E_1| = k$ and $|E_2| = m - k$. Denote the neighbors of $v$ by $u_1, \dots, u_k$. Then each $(v, u_i) \in E_1$ contributes at most $\text{deg }u_i$ to $s(G)$. Summing over all $e \in E_1$, the contribution of $E_1$ to $s(G)$ is at most $|E_1| + 2|E_2| = 2m - k$, since each edge in $E_1$ is counted once and each edge in $E_2$ twice by the degree sum. Now we evaluate the contribution of $E_2$. If the vertex $v$ were to be deleted, these $m-k$ edges would contribute at most $f(m-k)$ to the score. Adding vertex $v$ back increases the degree of each vertex in $V(G) \setminus \{v\}$ by at most one, increasing the contribution of each edge in $E_2$ by at most one, increasing the total contribution of $E_2$ by at most $|E_2| = m - k$. Adding this to the contribution of $E_1$ gives the desired inequality. $\square$ Lemma 3: For all positive integers $n$ we have $f\left(\frac{n(n-1)}{2}\right) = \frac{n(n-1)^2}{2}$. Proof: By taking the complete graph with $n$ vertices, we can see that the LHS is at least the RHS. Now we need to prove the other direction. We will use induction on $n$; the base case $n=1$ is trivial. Suppose $f\left(\frac{(n-1)(n-2)}{2}\right) = \frac{(n-1)(n-2)^2}{2}$. Now take a graph $G$ with $\frac{n(n-1)}{2}$ edges; note that $G$ has at least $n$ vertices. We would like to find a graph $G'$ such that $s(G') \ge s(G)$ and such that $G'$ has a vertex with degree at least $n-1$. Assume that the maximum degree of $G$ is at most $n-2$, since otherwise $G' = G$ works. Then $G$ has no dominant vertex, and as long as $G$ has more than $n$ vertices (which is always the case if $G$ is not the complete graph), $|E(G)| \le \frac{(|V(G)|-1)(|V(G)-2|)}{2}$, and we can apply Lemma 1 to shrink $G$ without decreasing the score. The process can be repeated until we get a $G'$ that works. Now we use Lemma 2 to bound $s(G)$. We have \[s(G) \le f\left(\frac{n(n-1)}{2} - (n-1)\right) + \frac{3n(n-1)}{2} - 2(n-1) = \frac{(n-1)(n-2)^2}{2} + \frac{3n(n-1)}{2} - 2(n-1),\]which is equal to the desired bound. $\square$ Finally, we will find $f(2017)$. Note that $2017 = \frac{64\cdot 63}{2} + 1$, and a graph $G$ with $2017$ edges must have at least $65$ vertices. We claim that it is optimal to choose $G$ to be the graph $M$, defined as the complete graph with $64$ vertices plus an extra edge leading to a vertex of degree $1$. If $G$ has a vertex with degree at least $64$, then we are done by applying Lemma 2 with that vertex, then using lemma 3 on $f(2017 - 64) = f\left(\frac{63 \cdot 62}{2}\right)$. Otherwise, $G$ cannot have a dominant vertex, and we modify $G$ without decreasing the score as follows: as long as $G$ has more than $65$ vertices, use Lemma $1$. Now $G$ has $65$ vertices. Then the average degree of $G$ is $\frac{2017 \cdot 2}{65} < 63$, and there is a vertex $v$ with degree $k \le 62$. Now delete all but one edge adjacent to $v$, and there are exactly enough edges to put edges back so that $G$ ignoring $v$ is a complete graph with $64$ vertices, turning $G$ into $M$. The contribution of any edge in $G$ not adjacent to $v$ did not decrease during this process. The contribution of each "moved" edge went from $k$ to $63$, which is an increase of at least $1$, and the total increase from all moved edges is at least $k-1$. On the other hand, the contribution of the one edge remaining adjacent to $v$ decreased by at most $k-1$, since the degree of $v$ decreased by this much.Therefore $s(G) \le s(M)$ as desired.

We re-phrase the problem in Graph Theory terms: "Consider a graph G with $2017$ edges. Then, we need the minimum possible value of $S(G)=\sum_{e=vw}\min(\text{deg }v, \text{deg }w)$." Construction: The answer is $127009$. The construction is to consider $65$ vertices with a $K_{64}$ and a dangling vertex. The answer is, indeed, $S(G) = 2016\cdot63 + 1 = 127009$. Hence, the construction is valid. Bound: This proof has two parts, one combinatorial and one algebraic. Combinatorial Part:= Let $G$ have $n$ vertices ($n>=65$) $v_1, v_2,..., v_n$ and let vertex $v_i$ have degree $d_i$. Then, by Handshake Lemma, $d_1 + d_2 + ... + d_n = 4034$. WLOG assume that $d_1 \geq d_2 \geq ... \geq d_n$. We try to find an upper bound for $S(G)$. Then, $d_2$ can appear as minimum in at most one edge. Note that in that case $v_1v_2$ is an edge. As a result, $d_3$ can appear as minimum at most two edges: only if $v_1v_3$ and $v_2v_3$ are edges. Going on like this, we see that $d_i$ can appear as minimum in at most $i-1$ edges for every $1\leq i\leq 64$. For $d_{65}$ we would've already have had $2016$ terms in the summation, so we can have at most one more. So, we get the bound: \[S(G) \leqslant d_2 + 2d_3 + ... + 63d_{64} + d_{65}\]Algebraic Part:= We claim that for any $x_1 \geq x_2 \geq ... \geq x_{65} \geq 0$ with $x_1 + x_2 + ... + x_{65} \leq 4034$, then \[x_2 + ... + 63x_{64} + x_{65} \leq 127010\]Proof. Note that we can increase $x_i$ if $x_1 + x_2 + ... + x_{65} < 4034$. So, assume that $x_1 + x_2 + ... + x_{65} = 4034$. For any indices $1\leq i<j\leq 64$ if we have $x_i > x_{i+1} \geq x_{j-1}>x_j$ then simply replace $(x_i, x_j)$ with $(x_i-1, x_j+1)$ and increase the sum while preserving the fact that $x_i$ are weakly decreasing. Keep doing this until we have that $x_i-x_{i+1}\leq 1$ for every $i\leq 64$. Now, if $x_{65}>4$ then replace $(x_1, x_2, x_3, x_4, x_{65})$ with $(x_1+1, x_2+1, x_3+1, x_4+1, x_{65}-4)$. Doing this strictly increases the LHS sum. Henceforth, assume that $x_{65}<=3$. We need to examine only four cases: Case 1: $x_{65}=3$. In this case, we set $x_{64}=62$ and $x_1 = x_2 = ... = x_{63} = 63$. In this case, we get LHS sum $= 63\cdot62\cdot63/2 + 62\cdot63 + 3 = 126948 < 127010$. Case 2: $x_{65}=2$. In this case, we set $x_1 = x_2 = ... = x_{64} = 63$. In this case, we get LHS sum $= 63\cdot63\cdot64/2 + 2 = 127010$. Case 3: $x_{65}=1$. In this case, we set $x_1=64$ and $x_2 = x_3 = ... = x_{64} = 63$. In this case, we get LHS sum $= 63\cdot63\cdot64/2 + 1 = 127009$. Case 4: $x_{65}=0$. In this case, we set $x_1 = x_2 = 64$ and $x_3 = ... = x_{64} = 63$. In this case, we get LHS sum $= 63\cdot(63\cdot64/2-1) + 64 = 127009$. So, our claim is true. We need to show that Case 2 is impossible. Suppose $v_{65}$ is adjacent to $v_{t_1}$ and $v_{t_2}$. So, the graph $G$ is a $K_{64}$ without edge $v_{t_1}v_{t_2}$ but instead we have $v_{t_1}v_{65}$ and $v_{t_2}v_{65}$ edges. Note that for this graph, we have $S(G) = 2\cdot62\cdot62 + 1891\cdot63 + 4 = 126825 < 127009$. The proof is complete. Remark: It can be easily shown that "Case 4" from the Algebraic Bounding does not exist.

Here goes the work: Convert the problem into graph, where dishes are vertices and there is an edge between two dishes if a mathematician orders both of them. Define $f(G)$ as: $$f(G) = \sum_{e \in G, e=(u, v)} \min(\deg(u), \deg(v))$$where $G$ is a simple graph. We wish to maximize $G$ while constraining the vertices. Let $G$ have $E = \binom{k}{2}+1$ edges. Label every edge $(u, v)$ with $\min(\deg(u), \deg(v))$. Def: In a graph $G$, a vertex $v \in G$ is called dominating if for every other vertex $u \in G$ ($u \neq v$), the edge $(u, v)$ exists in the graph $G$ (formally $(u, v)\in G$). We proceed with the following claim: Claim: For every graph $G$ with $E = \binom{k}{2}+1$ edges which has no dominating vertex, we have another graph $G'$ having same number of edges $E$ and $f(G') \ge f(G)$ along with $G'$ having a dominating vertex, for $k \ge 4$. Proof: Consider induction on the number of vertices on graph $G$ (denoted by $V$). - The Base Case $V = k+1$; Every vertex in graph $G$ has degree at-most $k-1$. Notice that, the average degree of a vertex in $G$: $$\frac{2m}{V} = \frac{k^2-k+2}{k+1} < k-1$$for all $k \ge 4$. Thus, consider a vertex $v$ of degree $d$, $1 \le d \le k-2$. Thus, every edge adjacent to $v$ has label of at-most $d$ and therefore: $$f(G) \le d \cdot d+(m-d)(k-1) \le \binom{k}{2}(k-1)+1.$$ Consider the inductive step, where we have $V=n+1$ vertices in $G$. Consider vertex $v$ of degree $d$ which is minimum ($0 \le d \le k-2$). Let vertices $v_1, v_2, \cdots, v_d$ be the adjacent vertices to $v$. Now, we delete every edge $(v, v_t)$ and make another new edge which wasnt created into graph $G$ at vertex $v_t$. Let this graph denote by $G_0$. Now, if there are any double edges formed due to this process, then we delete one of their occurrences and draw another edge which hasn't been drawn in $G_0$. Let the resulting graph denote by $G''$. Notice that: $$f(G'') \ge f(G_0) \ge f(G)$$as we are basically increasing at-least $d$ after removing vertex $v$. Due to inductive hypothesis, $G''$ has a dominating vertex and we are done. Due to a similar inductive argument as above, we have the following fact: Fact: For every graph $G$ with $E = \binom{k}{2}$ edges which has no dominating vertex, we have another graph $G'$ having same number of edges $E$ and $f(G') \ge f(G)$ along with $G'$ having a dominating vertex, for $k \ge 3$. Claim: $f(G) \le \binom{k}{2}(k-1)+1$ where $G$ is a graph which has $\binom{k}{2}+1$ edges, has a dominating vertex. Also, $f(G) \le \binom{k}{2}(k-1)$ where $G$ is a graph which has $\binom{k}{2}$ edges, has a dominating vertex. Proof: We again proceed by induction on the number of vertices $V$. Consider we have $V = n+1$ vertices in graph $G$ with $\binom{k}{2}+1$ edges. Let vertex $v$ denote one of its dominating vertex. Delete this vertex $v$ and the resulting graph be $H$ which has $E_h = \binom{k}{2}+1-n \le \binom{k-1}{2}$. Due to inductive hypothesis, $f(H) \le \binom{k-1}{2}(k-2)$. Let $v_1, v_2, \cdots, v_n$ be the vertices adjacent to $v$. Notice that: $$\sum \min(\deg(v), \deg(v_i)) = \sum \deg(v_i) = 2 E_h + n.$$Also, in sub-graph $H$, after adding vertex $v$, each edge's label increases by $1$. Thus: $$f(G) = (f(H)+E_h)+ 2 E_h + n \le \binom{k}{2}+1 + \binom{k-1}{2}(k-1) + 2 \binom{k-1}{2} = \binom{k}{2}(k-1).$$ Similarly, we have $f(G) \le \binom{k}{2}(k-1)$ where $G$ is a graph which has $\binom{k}{2}$ edges, has a dominating vertex, due to a similar inductive argument as above. Therefore the induction is complete and we are done.