Edge colouring distinguishing by sums for a complete graph

Question

Let $G=(V_G,E_G)$ will be a simple graph and $f:E\to\{1,...,k\}$ will be edge $k-$coloring. Denote $\sigma_f(x) = \sum_{xy\in E_G}f(xy)$ for $x \in V_G$ Consider a parameter $s(G) = \min\{k:\exists k-\textrm{coloring } f,\forall x,y\in V_G, x\ne y: \sigma_f(x)\ne\sigma_f(y) \}$, that we shall call level of irregularity. I want to show that $s(K_n) = 3$, where $K_n$ denotes a complete graph. It is clear that $s(K_3)=3$ (we have a triangle and we need to assign three different numbers to the edges). We can add the vertex and three edges with wages $1$ and obtain $s(K_4)=3$ then add another vertex and four edges with wages $3$ and obtain $s(K_5)= 3$. We can repeat addding vertices and $n-1$ edges once with wages $1$ and once with wages $3$ and it would seem that $s(K_n)=3$. But I struggle with more rigorous proof. I would be grateful for some hints.

Answer 1

Here is a slightly different phrasing of the same inductive step, but which is easier to verify.

Suppose there is a labeling of $E(K_n)$ with $1,2,3$ which is distinguishing by sums. We use it to construct a labeling of $E(K_{n+1})$ with the same property by adding a new vertex adjacent to all the old ones, and deciding on the labels of the newly created edges. Here is how we decide:

Case 1. The labeling of $K_n$ has no vertex with sum $n-1$.

In this case, put a label of $1$ on every new edge. The new vertex has a sum of $n$. The sums on the old vertices all increase by $1$, so they remain distinct from each other; by the case, none of them increase to $n$, so they are distinct from the sum on the last vertex, as well.

Case 2. The labeling of $K_n$ has no vertex with sum $3(n-1)$.

In this case, put a label of $3$ on every new edge. The new vertex has a sum of $3n$. The sums on the old vertices all increase by $3$, so they remain distinct from each other; by the case, none of them increase to $3n$, so they are distinct from the sum on the last vertex, as well.

Case 3. The labeling of $K_n$ has a vertex $v$ with sum $n-1$ and a vertex $w$ with sum $3(n-1)$.

This cannot be. For $v$ to have sum $n-1$, all edges incident on $v$ must have label $1$. For $w$ to have sum $3(n-1)$, all edges incident on $w$ must have label $3$. But edge $vw$ can only have a single label: it is $1$ or $3$, not both. So we are never in case 3; we are always in case 1 or case 2, where we do get a labeling of $E(K_n)$ which is distinguishing by sums.

---

When we start from the labeling of $E(K_3)$ which uses the labels $1, 2, 3$ each once, and follow the rule above, we will in fact continue on as in the question: we will alternate adding vertices with new edges labeled $1$, and adding vertices with new edges labeled $3$. Proving this, however, would require a strengthened induction hypothesis, because we need to know something about the structure of the old labeling. The phrasing I used avoids that.

Another approach we could take is to get rid of induction entirely. Let the vertices be $$u_1, u_2, u_3, v_1, w_1, v_2, w_2, v_3, w_3, \dots$$ in the order they are added. Then there is a non-inductive description of the labels we end up with:

• The labels on $u_1 u_2, u_1 u_3, u_2 u_3$ are specified by the base case.
• The label on an edge $v_i w_j$ is $1$ if $i>j$, and $3$ if $i \le j$.
• The label on every other edge with endpoint in $\{v_1, v_2, v_3, \dots\}$ is $1$.
• The label on every other edge with endpoint in $\{w_1, w_2, w_3, \dots\}$ is $3$.

By working out the sum at every vertex of the resulting graph, we can prove that the labeling defined in the bullet points above is distinguishing by sums.