Reducibility Is Context-Dependent: Compositional Prediction for Discharging Proofs of Edge Colorability

Many of the hardest theorems about coloring planar graphs are proved by the discharging method. The idea is simple. Give every vertex and face a numerical "charge" whose total is fixed by Euler's formula at a negative constant. Move charge around by local rules. Then show that if the graph contains none of a list of small "reducible" pieces, every element ends up with non-negative charge, which is impossible. A piece is reducible if a smallest counterexample cannot contain it, usually because any coloring of the graph with the piece shrunk can be extended back to the piece.

The bottleneck in such proofs is finding and certifying that list of pieces. Each reducibility check enumerates colorings of the piece's boundary, so its cost grows exponentially with boundary size, and the space of candidate pieces grows even faster. This note proposes a learned ranking model that predicts which candidate pieces are reducible before any exact check is run. The model is built on one observation borrowed from computer vision: whether a core piece is reducible depends on the boundary context around it, much as "red" looks different on wine and on a tomato. So the prediction should be composed from core and context, not scored from each separately.

In two sentences: we treat "is this configuration reducible for edge coloring?" as a compositional zero-shot recognition problem, pairing a core subgraph with its boundary context, and train a model that composes the two to predict reducibility on pairings it has never seen. The predictions only decide the order in which an exact verifier runs, so every resulting proof stays fully checked. The model's job is to cut the number of expensive verifier calls needed to assemble a complete discharging argument.

Core Claim

Reducibility for edge coloring behaves like a context-dependent attribute. The same core configuration can be reducible under one boundary type and irreducible under another. That boundary type means the pattern of edges leaving the piece and the degree constraints on their far endpoints. We claim three things. First, a predictor that factorizes reducibility into an independent core score and an independent boundary score will fail on held-out pairings, in the same way that naive attribute-times-object classifiers fail in vision. Second, composing a context-specific classifier from core and boundary representations will generalize to unseen pairings. Third, used as a ranking oracle inside an automated discharging loop, such a model substantially reduces the exact verification work needed to rediscover known unavoidable sets for edge-coloring theorems.

This is new relative to the closest work. Le combines discharging with linear programming (LP): given a list of configurations already chosen by hand, the LP optimizes the constants in a density bound. That work motivates this one, because it names manual enumeration of configurations as the remaining bottleneck. It does not propose, rank, or predict configurations. In vision, From Red Wine to Red Tomato: Composition with Context composes a classifier for an attribute–object pair from the two primitive classifiers using a learned network. We reuse that composition method, but point it at a mathematical label that has an exact ground truth. The research file contained no prior-work entry, and I found none, that applies learned compositional prediction to reducibility or to discharging proof search.

Why these three directions fit together

Edge-colorability verification supplies both the target theorems and the exact checker. Tait's equivalence connects 3-edge-coloring of bridgeless cubic planar graphs to the Four Color Theorem. Three results give real unavoidable sets that can serve as ground truth:

The recognition algorithm of Efficient Recognition of Subgraphs of Planar Cubic Bridgeless Graphs decides in $O(n^2)$ time whether a subcubic planar graph can be completed to a cubic bridgeless planar graph. That makes it a cheap sufficient test for 3-edge-colorability. It is not a necessary test: $K_{2,3}$ is 3-edge-colorable but cannot be completed this way. We use it only as a fast pre-filter that can certify "colorable" for reduced graphs. Its one-sided nature is itself a context effect the model must learn to see past.

Context-dependent attribute appearance supplies the learning formulation. The vision literature separates three families of models: independent primitives, operators that transform one primitive by another, as in Attributes as Operators, and classifiers conditioned on context, as in Learning Conditional Attributes for Compositional Zero-Shot Learning. That split maps directly onto a testable hypothesis about how reducibility decomposes.

Research Program

Stage 1: build the dataset. We enumerate small configurations for three settings: subcubic planar pieces for 3-edge-coloring, pieces for 6-regular plane multigraphs, and pieces for 7-regular planar graphs. Each configuration is split into a core, meaning its internal vertices and edges, and a boundary context, meaning its ring of outgoing edges, their cyclic order, and degree annotations on the outer endpoints.

Stage 2: label every pair exactly. An exact reducibility checker labels each (core, context) pair. The checker enumerates boundary precolorings that extend in the reduced graph and tests whether each extends to the configuration. It is implemented with a SAT solver, with Kempe-chain recoloring for the stronger variants. Labels are exact, so the dataset has no annotation noise, which is rare for a compositional benchmark.

Stage 3: split for zero-shot evaluation. Training and test sets are split in the compositional zero-shot style. Every core and every context appears in training, but some pairings appear only in test.

Stage 4: compare model families. We compare four models:

  • an independent-primitive model, which scores the core and the context separately and sums the scores;
  • an operator model, in which the context acts as a learned matrix on the core embedding;
  • a model-space composer following Misra et al., which maps a core classifier and a context classifier to a pair-specific classifier;
  • a monolithic graph neural network (a network that passes messages along graph edges) that reads the whole configuration at once.

Core and context encoders are graph neural networks over the planar embedding.

Stage 5: plug the model into proof search. The chosen model becomes the ranking oracle in an automated discharging loop built on Le's LP formulation. The loop repeats four steps:

  1. Propose discharging rules and a candidate configuration list.
  2. Have the LP report which configurations must be excluded for all final charges to be non-negative.
  3. Rank the missing candidates by predicted reducibility.
  4. Send them to the exact checker in that order.

The loop stops when the LP certifies that the current list is unavoidable under the current rules.

Baselines

The naive reference point is exhaustive verification in a fixed canonical order, sorted by boundary size and then by vertex count. It uses the same exact checker, the same LP loop, and the same wall-clock budget. Every other method is measured by how many checker calls, and how much checker time, it saves relative to this. No reported result found on Lacuna for automated reducible-set search cost on any of the target theorems. So this baseline is measured fresh, not quoted.

The strongest non-learned competitor is a handcrafted ranking that encodes the heuristics discharging proofs actually use:

  • low ring size;
  • high density of low-degree vertices, as in the degree-based eliminations of Xie and Yu;
  • a count of boundary precolorings that the completion test of Efficient Recognition already certifies.

It is the strongest competitor because it costs nothing to train and reflects decades of human practice. It runs on the identical candidate stream. Beating it means at least a 2× reduction in checker time to certify a complete unavoidable set in two of the three settings.

The strongest learned competitor is the monolithic graph neural network. It sees exactly the same information as the compositional model and is trained on the same labels with the same hyperparameter search budget. It is the ablation that isolates the key ingredient. If it matches the composer on held-out pairings, the compositional claim fails. The independent-primitive model is the second ablation. It tests whether context dependence exists at all.

For reference in the vision domain, we report compositional models on their native attribute–object benchmarks only as a sanity check of the implementations. The file gives no numbers for those benchmarks, so no reported result found on Lacuna for the reference accuracy.

Why not just…?

Why not just run the exact checker on everything? If checks were cheap, ranking would be pointless. Our first experiment measures checker cost against ring size. We restrict the claim to the regime where a single check takes seconds to minutes and candidates number in the tens of thousands. That regime is where the degree-7 and degree-6 proofs live. If exhaustive search stays within budget for all three targets, we report that honestly, and the contribution shrinks to the compositional-generalization finding alone.

Why not just use the handcrafted heuristics? They are a serious threat for small ring sizes, where human intuition was tuned. They are weakest exactly where context matters: the same core can flip from reducible to irreducible when the boundary degree pattern changes. The pair-level analysis in the experiments measures how often such flips occur. If flips are rare, heuristics should win and we will say so.

Why not just train one graph network on the whole configuration? This is the most likely real alternative. Its weakness should appear only on unseen core–context pairings. Misra et al. found the analogous failure in vision, but a whole-graph network is not a late-fusion model, so the analogy may not carry over. The held-out-pairing split settles this directly. Tying on it counts as a negative result for our central claim.

Why not just extend the LP to choose configurations? An LP optimizes over a fixed list, so selecting configurations would make it a mixed-integer program over an exponential candidate space. The LP already tells us which gaps need filling. It cannot tell us which fillers will verify.

Proposed Experiments

Experiment 1: does context dependence exist? On the subcubic setting, we measure the fraction of cores whose reducibility label changes across the contexts they appear in. The analogous measure is also computed for the degree-6 and degree-7 settings. A flip rate near zero kills the premise before any modeling.

Experiment 2: zero-shot prediction. We report area under the precision-recall curve for reducibility on held-out pairings, and separately on seen pairings, for all four model families. The decisive check is the gap on held-out pairings between the composer and both the independent and monolithic models.

Experiment 3: rediscovery. Starting only from the charge assignment and rule templates, the loop must reassemble an unavoidable set for 3-edge-coloring of projective planar cubic graphs and for the degree-7 planar result. Success is scored against the configurations those papers report, and the key metric is total checker time relative to the canonical and heuristic baselines.

Experiment 4: a harder target. As a stretch goal, we run the loop on fixed-degree subclasses at the intermediate-degree frontier (maximum degree 4 or 5) left open in the edge-coloring literature. Any certified unavoidable set found there would be an actual new theorem, checkable independently of the model.