2026-09-05T11:58:21Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:25828 2026-06-23T12:59:08Z ddc:004 open_access

Disproving Two Conjectures on the Hamiltonicity of Venn Diagrams Brenner, Sofia Kleist, Linda Mütze, Torsten Rieck, Christian Verciani, Francesco Venn diagram Winkler’s conjecture Hamilton cycle perfect matching hypercube In 1984, Winkler conjectured that every simple Venn diagram with n curves can be extended to a simple Venn diagram with n+1 curves. This conjecture is equivalent to the statement that the dual graph of any simple Venn diagram has a Hamilton cycle. In this work, we construct counterexamples to Winkler’s conjecture for all n ≥ 6. As part of this proof, we computed all 3.430.404 simple Venn diagrams with n = 6 curves (even their number was not previously known), among which we found 72 counterexamples. We also disprove another conjecture about the Hamiltonicity of the arrangement graph of a Venn diagram. Specifically, while working on Winkler’s conjecture, Pruesse and Ruskey proved that this graph has a Hamilton cycle for every simple Venn diagram with n curves, and conjectured that this also holds for non-simple diagrams. We construct counterexamples to this conjecture for all n ≥ 4. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Sofia Brenner and Linda Kleist and Torsten Mütze and Christian Rieck and Francesco Verciani 2026 Is Part Of LIPIcs, Volume 367, 42nd International Symposium on Computational Geometry (SoCG 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2026.22 urn:nbn:de:0030-drops-258285 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2026.22 eng https://creativecommons.org/licenses/by/4.0/legalcode