A Proof of the Modular Edge-Graceful Trees Conjecture

Let \( G \) be a connected graph of order \( n \geq 3 \) and size \( m \), and let \( f: E(G) \to \mathbb{Z}_n \) be an edge labeling of \( G \). Define an induced vertex labeling \( f’: V(G) \to \mathbb{Z}_n \) in terms of \( f \) by \( f'(v) = \sum_{u \in N(v)} f(uv) \), where the sum is computed in \( \mathbb{Z}_n \). If \( f’ \) is one-to-one, then \( f \) is called a modular edge-graceful labeling and \( G \) is a modular edge-graceful graph. It is known that no connected graph of order \( n \geq 3 \) with \( n \equiv 2 \pmod{4} \) is modular edge-graceful. A 1991 conjecture states that every tree of order \( n \) where \( n \not\equiv 2 \pmod{4} \) is modular edge-graceful. In this work, we show that this conjecture is true and furthermore that a nontrivial connected graph of order \( n \) is modular edge-graceful if and only if \( n \not\equiv 2 \pmod{4} \). The modular edge-gracefulness \(\text{meg}(G)\) of a connected graph \( G \) of order \( n \geq 3 \) is the smallest integer \( k \geq n \) for which there exists an edge labeling \( f: E(G) \to \mathbb{Z}_k \) such that the induced vertex labeling \( f’: V(G) \to \mathbb{Z}_k \) is one-to-one. It is shown that \(\text{meg}(G) = n+1\) for every connected graph \( G \) that is not modular edge-graceful.