# Edge colouring distinguishing by sums for a complete graph

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.

• In human-readable form: an edge labeling is "distinguishing by sums" if, when we label each vertex with the sum of the labels of its incident edges, adjacent vertices get different labels. The parameter $s(G)$ is the least $k$ such that an edge labeling of $G$ with $\{1,\dots,k\}$ exists which is distinguishing by sums. Commented Aug 28, 2023 at 14:06

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.