Problem A. 870. (January 2024)

A. 870. We label every edge of a simple graph with the difference of the degrees of its endpoints. If the number of vertices is \(\displaystyle N\), what can be the largest value of the sum of the labels on the edges?

Proposed by Dániel Lenger and Gábor Szűcs, Budapest

(7 pont)

Deadline expired on February 12, 2024.

Let \(\displaystyle v_1\) denote the number of edges connecting vertex \(\displaystyle v\) to a vertex with a smaller degree, and \(\displaystyle v'_1\) denote the number of edges connecting vertex \(\displaystyle v\) to a vertex with smaller or equal degree. \(\displaystyle v_2\) and \(\displaystyle v_2'\) are defined similarly. The degree of \(\displaystyle v\), \(\displaystyle d(v)\) can be written as \(\displaystyle v_1+v'_2\) and \(\displaystyle v'_1+v_2\).

Let's assume that graph \(\displaystyle G\) is extremal. We will prove several observations about \(\displaystyle G\).

Adding an edge. Suppose that \(\displaystyle k\) and \(\displaystyle n\) are two unconnected vertices of the graph with \(\displaystyle d(k)\le d(n)\). What happens to the weights on the edges if we add edge \(\displaystyle kn\) to \(\displaystyle G\)? The weights will increase by one on those edges that connect the vertices to a vertex with a degree that's not larger, and it will decrease by 1 on those edges that connect the vertices to a vertex with a larger degree. This gives a total of \(\displaystyle n'_1+k'_1-n_2-k_2\). Additionally, edge \(\displaystyle kn\) will have a weight of \(\displaystyle d(n)-d(k)\). Therefore the total change is

\(\displaystyle d(n)-d(k) + n_1'+ k_1' - n_2 - k_2 = n_1' + n_2 - k_1' - k_2 + n_1'+ k_1' - n_2 - k_2 = 2(n_1' - k_2).\)

Since \(\displaystyle G\) was extremal, \(\displaystyle 2(n'_1-k_2)\le 0\), and thus \(\displaystyle n'_1\le k_2\).

Deleting an edge. Let \(\displaystyle k\) and \(\displaystyle n\) be two connected vertices with \(\displaystyle d(k)\le d(n)\). What happens when we delete edge \(\displaystyle kn\)? Weights on edges connecting the vertices to a vertex with a degree that is not larger will increase by 1, and on edges connecting the vertices to a vertex with a smaller degree will decrease by 1. The weight of the deleted edge was \(\displaystyle d(n)-d(k)\). The total change is

\(\displaystyle d(k) - d(n) + n_2' + k_2' - n_1 - k_1 = k_1 + k_2' - n_1 - n_2' + n_2'+ k_2' - n_1 - k_1 = 2(k_2' - n_1).\)

This implies \(\displaystyle k'_2\le n_1\), since \(\displaystyle G\) is extremal.

Cherry. Let three vertices of the graph be \(\displaystyle u\), \(\displaystyle t\) and \(\displaystyle a\), where \(\displaystyle ua\) is not an edge, \(\displaystyle ta\) is an edge, and \(\displaystyle d(u),d(t)\le d(a)\). Adding edge \(\displaystyle ua\) yields \(\displaystyle a'_1\le u_2\), and deleting edge \(\displaystyle ta\) yields \(\displaystyle t'_2\le a_1\). Putting these together we get \(\displaystyle t_2'\le a_1\le a'_1\le u_2\), i.e. \(\displaystyle t_2'\le u_2\).

Reverse cherry. Let \(\displaystyle m\), \(\displaystyle u\) and \(\displaystyle t\) be three vertices with \(\displaystyle mu\) not being an edge, \(\displaystyle mt\) being an edge and \(\displaystyle d(m)\le d(u),d(t)\). Adding edge \(\displaystyle mu\) yields \(\displaystyle u'_1\le m_2\), deleting edge \(\displaystyle mt\) yields \(\displaystyle m'_2 \le t_1\). Combining these proves \(\displaystyle u'_1\le t_1\).

Partitioning from the minimal degree. Let \(\displaystyle m\) be a vertex with a minimal degree. We can assume that \(\displaystyle d(m)>0\): adding an edge from an isolated point will not decrease the total weight. Let \(\displaystyle A\) denote the set of vertices not connected to \(\displaystyle m\), while \(\displaystyle B\) denote the set of vertices connected to \(\displaystyle m\). Applying the reverse cherry argument yields \(\displaystyle a'_1\le b_1\) for any \(\displaystyle a\in A\) and \(\displaystyle b\in B\).

Let's assume there exists \(\displaystyle n\in A\) and \(\displaystyle k\in B\) satisfying \(\displaystyle d(n)>d(k)\), implying the existence of vertex \(\displaystyle x\) that is connected to \(\displaystyle n\) and not connected to \(\displaystyle k\). We also know that \(\displaystyle n'_1\le k_1\). Let's consider cases based on the value of \(\displaystyle d(x)\):

• \(\displaystyle d(x)\ge d(n)\). Applying the cherry argument for \(\displaystyle k,n,x\) implies \(\displaystyle n'_2\le k_2\). We get a contradiction: \(\displaystyle d(n)=n'_1+n_2\le n'_1+n'_2\le k_1+k_2\le k'_1+k_2=d(k)\).
• \(\displaystyle d(k)<d(x)<d(n)\). In this case, edges alternate in cycle \(\displaystyle m--k--x--n\). Let's delete edges and add the missing edges in this cycle. Degrees are unchanged in \(\displaystyle G\), however, the weight of the cycle increases: \(\displaystyle (d(n)-d(x))+(d(k)-d(m))<(d(n)-d(m))+(d(x)-d(k))\).
• \(\displaystyle d(x)\le d(k)\). Let's check cycle \(\displaystyle m--k--x--n\) again: in this case, swapping edges and non-edges will retain the weight of \(\displaystyle G\), since \(\displaystyle (d(n)-d(x))+(d(k)-d(m))=(d(n)-d(m))+(d(k)-d(x))\). However, vertices \(\displaystyle n\) and \(\displaystyle k\) swapped places in \(\displaystyle A\) and \(\displaystyle B\), therefore we can assume that the degrees in \(\displaystyle A\) cannot be greater than the degrees in \(\displaystyle B\).

From now on, we assume \(\displaystyle d(a)\le d(b)\) for all \(\displaystyle a\in A\), \(\displaystyle b\in B\).

Let's check whether it's possible to have an edge in \(\displaystyle A\). Suppose that \(\displaystyle p,q\in A\) and \(\displaystyle pq\) is an edge, moreover \(\displaystyle d(p)\le d(q)\). Using the reverse cherry argument \(\displaystyle p\) is also connected to all the vertices in \(\displaystyle B\), since \(\displaystyle q_1\le b_1\). On the other hand, applying the cherry argument for triple \(\displaystyle m\), \(\displaystyle p\) and \(\displaystyle q\) implies \(\displaystyle |B|+1\le p'_2\le m_2=|B|\). This is a contradiction, thus there are no edges inside \(\displaystyle A\).

Since \(\displaystyle m\) is minimal, every vertex in \(\displaystyle A\) has to be connected to every vertex in \(\displaystyle B\).

Now let's check whether is possible that two vertices are not connected inside \(\displaystyle B\). Let's assume that \(\displaystyle r,s\in B\), \(\displaystyle rs\) is not an edge, \(\displaystyle d(r)\le d(s)\). Applying the reverse cherry argument for \(\displaystyle m\), \(\displaystyle r\) and \(\displaystyle s\) implies \(\displaystyle |B|=m'_2\le r_2\le |B|-1\), contradiction.

Ultimately we've showed there is an extremal graph with the following structure: the vertices of a complete graph are connected to the vertices of an empty graph. If the number of vertices in the complete graph is \(\displaystyle X\) and \(\displaystyle Y\) is the empty graph, then the total weight of the graph is

\(\displaystyle X(X-1)/2 \cdot 0 + XY \cdot (Y-1) = XY(Y-1).\)

Let's check two consecutive values, \(\displaystyle XY(Y-1)\) and \(\displaystyle (X-1)(Y+1)Y\): their difference is \(\displaystyle (2X-Y-1)Y\), therefore increasing \(\displaystyle Y\) will increase the weight until \(\displaystyle Y+1<2X\), thus \(\displaystyle N+1<3X\) and \(\displaystyle 3Y<2N-1\). This means that the extremal value will be reached when \(\displaystyle X=\lfloor \frac{N+1}{3} \rfloor\), \(\displaystyle Y=\lceil \frac{2N-1}{3} \rceil\) (if \(\displaystyle N\) is 2 mod 3, there will be two choices for \(\displaystyle X\) and \(\displaystyle Y\)).

Statistics:

12 students sent a solution.
7 points:	Duchon Márton, Varga Boldizsár, Wiener Anna.
3 points:	3 students.
2 points:	3 students.
1 point:	1 student.
0 point:	2 students.

Problems in Mathematics of KöMaL, January 2024