← All problems

The edge-irregularity deletion conjecture

1 year old · traced to

Let G=(V,E)G=(V,E) be a connected graph, and let m=∣E∣m=|E| be its number of edges. An edge-irregulator of GG is a set S⊆ES\subseteq E such that G−SG-S is locally irregular, meaning that every edge of G−SG-S joins vertices of different degrees; write Ie(G){\rm I}_e(G) for the minimum possible size of an edge-irregulator. Edge-irregularity deletion conjecture. There is an absolute constant c≥1c\geq 1 such that, for every connected graph GG with mm edges,

Ie(G)≤13m+c.{\rm I}_e(G)\leq \frac{1}{3}m+c.

The conjecture is motivated by the behaviour of cycles, where deleting one edge can resolve at most three local degree conflicts, while small graphs such as K2K_2 and C4C_4 show that an additive constant is necessary. The general bound remains open in the source paper.

References
  1. Julien Bensmail, Noémie Catherinot, Foivos Fioravantes, Clara Marcille and Nacim Oijid, “Graph Irregularity via Edge Deletions”, arXiv:2511.14514 (2025).

Progress summary

Refreshed
Open · progress reported

The published literature leaves the conjecture open, but an unverified community submission claims to give a counterexample.

Bensmail, Catherinot, Fioravantes, Marcille, and Oijid proposed the conjecture in their November 18, 2025 paper: a universal additive constant should bound the number of deleted edges by one third of the total, for every connected graph.

Known results

The paper proves the conjecture for several families, including trees, paths, cycles, and complete graphs, with exact formulas for paths and cycles. It also constructs graphs from twice-subdivided connected graphs satisfying Ie(G)≥13m\mathrm{I}_e(G)\geq \frac{1}{3}m, and identifies further open questions concerning complete graphs and extremal locally irregular graphs.

Community submission (unverified), November 7, 2026

A submitted argument claims that, for every integer t≥2t\geq 2, there is a connected simple graph with 6t+16t+1 vertices and 8t8t edges having Ie(G)=3t\mathrm{I}_e(G)=3t, which would refute the conjecture for every fixed constant cc. The cited preprint and proof have not received independent mathematical verification here.

Current status (as of November 2026): The conjecture remains open in the published literature; a community submission claims a counterexample, but that claim is unverified.

Sources

Solutions 1

Unbounded excess over the one-third edge-irregulator boundSee full solutionHide full solution

Result and scope. For every integer t>=2, a connected simple graph with 6t+1 vertices and 8t edges has exact edge-irregulator minimum 3t. Hence no real absolute c>=1 satisfies I_e(G)<=|E(G)|/3+c for every connected finite simple graph.

Complete proof: Unbounded excess over the one-third edge-irregulator bound · PDF.

The paper page contains the proof-source JSON and extractor. The paper states the exact formalization, source interpretation, and trust limits. This is an AI-assisted preprint; internal review is not external peer review and no worldwide priority is claimed.