How to make a random graph irregular

An irregular edge labeling of a graph G = ( V, E ) is a weight assignment f: E→ N such that the sums f + (v):= Σ v∈e∈E f(e) are pairwise distinct. If such labelings exist in G, then the value of min f Σ e∈E ( f (e) ‐ 1) measures the minimum number of edges needed to make G irregular. We prove that this minimum for the random graph G(n, p ) with n vertices and edge probability p = p(n) is equal to n 2 /4 + o(n 2 ) as n→∞ , whenever p(n)‐n 2/3 →∞. This asymptotic result is deduced from a general estimate (valid for every graph) involving vertex degrees and the size of largest triangle packings. © 1995 John Wiley & Sons, Inc.