The paper disproves a long-standing conjecture in graph theory about a property called the bondage number. To understand what this means, start with domination: in a graph (a collection of dots connected by lines), a dominating set is a group of dots such that every dot in the graph is either in the group or directly connected to one that is. The domination number is simply how small you can make such a group. The bondage number then asks: how few connections do you need to remove from the graph before that minimum group size is forced to go up? Ulrich Teschner conjectured in the 1990s that this bondage number can never exceed one and a half times the maximum number of connections any single dot has.
The authors construct a specific small graph with 18 dots and 27 connections that breaks this conjecture. The graph has a maximum of 3 connections per dot, so Teschner's bound would predict a bondage number of at most 4. But the authors show the bondage number is actually 5, meaning you need to remove at least 5 connections before the minimum dominating group grows. They first prove the domination number is 6 by carefully counting across the graph's structure, then show that removing one specific set of 5 connections forces it up to 7.
The hardest part of the proof is showing that no set of just 4 removals can raise the domination number, which requires ruling out thousands of possible combinations. The authors handle this rigorously by cataloguing all 297 minimum dominating sets of the graph, then checking by exhaustive computation that for every possible group of 4 connections you might remove, at least one of those 297 sets still works as a dominating set. The entire verification relies only on basic counting and set operations, and the authors include the complete checking program in an appendix so anyone can independently confirm the result.