Assign node labels to maximize the total edge sum

Rewrite the objective. Each edge (u, v) contributes label(u) + label(v).
Summing over all edges, a node x appears once for every edge touching it, so

total = sum over nodes x of label(x) * degree(x)

The graph structure no longer matters, only the degree of each node. The task
is now: pair the labels 1..n with the degrees to maximize the sum of products.

Brute force. Try all n! labelings and recompute the sum. Fine for
n <= 8, useless beyond that. Worth saying aloud only to set up the
reduction.

Optimal: greedy by degree. Sort nodes by degree ascending and give the
i-th node (1-indexed) label i. The largest label goes to the busiest node.

Why it works (exchange argument, the rearrangement inequality): suppose an
optimal labeling gives nodes a, b labels la < lb while
deg(a) > deg(b). Swapping their labels changes the total by
(lb - la) * (deg(a) - deg(b)) > 0, so the original was not optimal. Hence
some optimal labeling has labels sorted in the same order as degrees. Ties in
degree can be broken any way; the sum is the same.

Invariants.

• Degrees always sum to 2 * len(edges); a quick sanity check.
• Isolated nodes (degree 0) still consume a label. They should get the
  smallest labels, which the sort does automatically.

Counting sort. Degrees lie in [0, n - 1], so a bucket count replaces the
comparison sort and gives O(n + m) overall.

from typing import List, Tuple


def max_edge_sum(n: int, edges: List[List[int]]) -> int:
    """Max over labelings (a permutation of 1..n) of sum of label(u)+label(v) per edge."""
    degree = [0] * n
    for a, b in edges:
        degree[a] += 1
        degree[b] += 1
    degree.sort()
    return sum(label * d for label, d in enumerate(degree, start=1))


def max_edge_sum_linear(n: int, edges: List[List[int]]) -> int:
    """Same answer in O(n + m) using a counting sort over degrees (0..n-1)."""
    degree = [0] * n
    for a, b in edges:
        degree[a] += 1
        degree[b] += 1
    bucket = [0] * n  # bucket[d] = number of nodes with degree d
    for d in degree:
        bucket[d] += 1
    total, label = 0, 1
    for d in range(n):
        for _ in range(bucket[d]):
            total += label * d
            label += 1
    return total


def best_labeling(n: int, edges: List[List[int]]) -> Tuple[int, List[int]]:
    """Return (max sum, labels) where labels[x] is the label given to node x."""
    degree = [0] * n
    for a, b in edges:
        degree[a] += 1
        degree[b] += 1
    order = sorted(range(n), key=lambda x: degree[x])
    labels = [0] * n
    for label, node in enumerate(order, start=1):
        labels[node] = label
    total = sum(labels[a] + labels[b] for a, b in edges)
    return total, labels


if __name__ == "__main__":
    from itertools import permutations

    def brute(n: int, edges: List[List[int]]) -> int:
        best = 0
        for perm in permutations(range(1, n + 1)):
            best = max(best, sum(perm[a] + perm[b] for a, b in edges))
        return best

    star = [[0, 1], [0, 2], [0, 3]]
    assert max_edge_sum(4, star) == 4 * 3 + 1 + 2 + 3 == 18
    assert max_edge_sum(3, []) == 0
    assert max_edge_sum(2, [[0, 1]]) == 3
    path = [[0, 1], [1, 2], [2, 3], [3, 4]]
    assert max_edge_sum(5, path) == 27
    assert max_edge_sum_linear(5, path) == 27
    assert best_labeling(4, star)[0] == 18 and best_labeling(4, star)[1][0] == 4

    import random
    for _ in range(300):
        n = random.randint(1, 6)
        pairs = [[a, b] for a in range(n) for b in range(a + 1, n)]
        edges = random.sample(pairs, random.randint(0, len(pairs)))
        expected = brute(n, edges)
        assert max_edge_sum(n, edges) == expected
        assert max_edge_sum_linear(n, edges) == expected
        assert best_labeling(n, edges)[0] == expected
    print("ok")

With n nodes and m edges:

• max_edge_sum: O(m + n log n) time, O(n) extra space.
• max_edge_sum_linear: O(m + n) time, O(n) extra space.
• best_labeling: O(m + n log n) time, O(n) space for the labels.

The answer can reach about n * 2m; Python integers do not overflow, but in
Java or C++ use a 64-bit accumulator.

• n = 4, edges [[0,1],[0,2],[0,3]] (star) -> 18. Center gets label 4
  (degree 3), leaves get 1, 2, 3.
• n = 5, edges [[0,1],[1,2],[2,3],[3,4]] (path) -> 27. Sorted degrees
  [1,1,2,2,2] give 1*1 + 2*1 + 3*2 + 4*2 + 5*2.
• n = 2, edges [[0,1]] -> 3.
• n = 3, no edges -> 0.
• n = 1, no edges -> 0.
• n = 4, complete graph K4 (6 edges) -> every degree is 3, answer
  3 * (1+2+3+4) = 30, any labeling works.
• Isolated nodes: n = 5, edges [[3,4]] -> 4 + 5 = 9; nodes 0..2 take
  labels 1..3 and contribute nothing.
• Repeated edge [[0,1],[0,1]] with n = 2 (if multi-edges are allowed) ->
  6; the degree count handles it with no special case.

1. Return the labeling, not just the sum. Sort node indices by degree and
   assign labels in that order (best_labeling). Mention that ties make the
   labeling non-unique.
2. Weighted edges. If edge (u, v) has weight w and contributes
   w * (label(u) + label(v)), replace degree with weighted degree
   (sum of incident weights) and sort by it. The exchange argument holds even
   with negative weights, since the rearrangement inequality only needs the
   coefficients sorted.
3. Edge value is label(u) * label(v) instead of a sum. The objective no
   longer separates per node; it becomes a quadratic assignment problem
   (NP-hard in general). Discuss brute force or bitmask DP for small n,
   and heuristics (high labels on a dense core) otherwise. Recognizing the
   change in difficulty is the point.
4. Labels are a given multiset (or any set of values), not 1..n. Sort
   the values and pair them with sorted degrees; same proof.
5. Edges arrive as a stream / graph too large for memory. Only the degree
   array is needed; keep n counters, one pass over the edge stream. For
   sharded edges, compute partial degree arrays per shard and sum them.
6. Minimize instead. Pair the largest label with the smallest degree
   (sort degrees descending).

Mid-level (L4)

• Sees that each node contributes label * degree and that edges matter only
  through degrees.
• Implements degree counting and the sort-then-multiply correctly.
• Handles isolated nodes and an empty edge list.

Senior (L5)

• Justifies the greedy with an exchange argument or the rearrangement
  inequality rather than "it seems right".
• States O(m + n log n) and offers the counting-sort O(n + m) version
  since degrees are bounded by n - 1.
• Notes 64-bit overflow risk in fixed-width languages; handles weighted-edge
  and return-the-labeling follow-ups quickly.

Staff (L6+)

• Explains which objective changes keep the problem separable (sums, weights,
  arbitrary label sets) and which break it (products → quadratic assignment),
  and what that means for the approach.
• Discusses streaming or distributed degree counting for very large graphs.
• Writes a brute-force cross-check for small n to validate the greedy.