# Which complete graphs are (edge) magic?

A magic labeling of a simple graph $G$ is a labeling of the edges of $G$ with distinct positive integers such that the sum of the labels of the edges incident to a vertex is the same for each vertex. A graph that admits a magic labeling is said to be magic.

I found a characterization due to Stewart that the complete graph $K_n$ is supermagic if and only if $(n\geq6\text{ and }n\not\equiv0\mod{4})$ or $n=2$, and supermagic graphs are magic, but I can't seem to find a theorem deciding which complete graphs are merely magic.

• You brought up supermagic but didn't define it. What is the definition of supermagic? – user2566092 Oct 8 '13 at 20:38
• It's a graph with a supermagic labeling, which is a magic labeling in which the positive integers used are consecutive. – Jeh Oct 8 '13 at 20:41

Theorem $4.7$ of M. Doob, ‘Characterizations of regular magic graphs’, J. Combin. Theory, Ser. B $25$ $(1978)$ $94$-$104$ says that if $G$ is a regular graph with degree $d>4$ and $n$ vertices, then $G$ is magic if $d>\frac{n}2$. Since $n-1>\frac{n}2$ for $n>2$, this implies that $K_n$ is magic for all $n\ge 6$. Clearly $K_2$ is also magic and $K_3$ is not. Theorem $4.3(ii)$ of the same paper implies that $K_4$ is not magic, and unless I’m missing something, Theorem $4.3$ in its entirety implies that $K_5$ is magic.

• I'm working on a labelling for $K_5$ because I've realised that the reference I found misses it out entirely, but I can't see where the construction would break down. – Peter Taylor Oct 8 '13 at 21:03
• @Peter: Now that I’ve looked at the construction, I think that it does work for $K_5$: every pair of edges of $K_5$ is separated by a $4$-cycle. (By the way, you’ve a typo in the spoiler block after tweak: you have $3k$ instead of $3^k$.) – Brian M. Scott Oct 8 '13 at 21:13
• It does work, and in fact it only takes the $4$ lexicographically first $4$-cycles. Thanks for the erratum, will correct. – Peter Taylor Oct 8 '13 at 21:16

It's strange that you can't find it, because the first page of results that Google gives me for magic graph include this set of exercises. Your question is exercise 1.3a.

Spoiler:

$K_n$ is magic for $n=2$ and $n\ge 5$.

(Note: this corrects the reference).

Leaving aside the small cases,

the proof for $n\ge 5$ is by the following construction. Since the graph is regular, we may consider arbitrary weights (not necessarily positive) and later add a suitably large constant to all of the edges.

I'm going to make a tweak to the proof.

Enumerate the cycles of length 4 that are contained in our graph, assigning them numbers from $1$ to $N$ (where $N$ is the total number of these cycles). Let the $k$th such cycle contribute $\pm 3^k$ (alternating) to its edges.

Let us check that this set of weights is magic. The total weight of the edges adjacent to every vertex is $0$, because the contribution of each cycle to this sum is $0$, so it suffices for the weights to be distinct. But for any pair of edges, there exists at least one cycle of length $4$ which includes only one of them. Therefore the sums of weights determined by the cycles are not equal, because the weights obtained by our construction may be regarded as $N$-digit balanced ternary numbers and so two edges can only have the same weight if they share all their $4$-cycles.