Graphic matroids with connectivity constraints
Abstract
In 1959, Tutte proved that a matroid can be realised by a graph if and only if it does not have a minor isomorphic to U2,4, F7, F7*, M*(K5) or M*(K3,3). In this paper, we extend this theorem to determine when it is possible to find a graphic realisation G of a matroid M, subject to a list of additional constraints of the following form: a subset F of the elements of M must induce a connected subgraph of G. We prove that a connected matroid with such constraints---called a `constraint matroid'---is realisable as a graph satisfying those constraints if and only if it does not contain as a minor one of the constraint matroids from a given list: that is, the original $5$ matroids of Tutte, a further $9$ sporadic constraint matroids, and two well-behaved infinite families. Matroids realisable as graphs appear famously in Whitney's planarity criterion: Carmesin proved an extension of Whitney's planarity criterion to the embeddability of local simply connected $2$-complexes into ℝ3. An application of our theorem is an extension of this theorem beyond the simply connected regime.
Related
- Nice Partitions of Signed-Graphic Arrangements Are Inductive Factorizations
- Sufficiency of Hall's Condition for Graphic List Coloring
- TASTE: A Designer-Annotated Multi-Dimensional Preference Dataset for AI-Generated Graphic Design
- Nice Partitions, Supersolvability, and Freeness in Deformations of Graphic Arrangements
- Graphic additive bases and graph flows
BibTeX
@misc{turner2026graphic,
title = {{Graphic matroids with connectivity constraints}},
author = {Will J. Turner},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.01841},
eprint = {2611.01841},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.01841},
}
RIS
TY - UNPB
TI - Graphic matroids with connectivity constraints
AU - Will J. Turner
PY - 2026
DA - 2026/11/01
PB - arXiv
DO - 10.48550/arxiv.2611.01841
UR - https://arxiv.org/abs/2611.01841
AB - In 1959, Tutte proved that a matroid can be realised by a graph if and only if it does not have a minor isomorphic to U_2,4, F_7, F_7^*, M^*(K_5) or M^*(K_3,3). In this paper, we extend this theorem to determine when it is possible to find a graphic realisation G of a matroid M, subject to a list of additional constraints of the following form: a subset F of the elements of M must induce a connected subgraph of G. We prove that a connected matroid with such constraints---called a `constraint matroid'---is realisable as a graph satisfying those constraints if and only if it does not contain as a minor one of the constraint matroids from a given list: that is, the original $5$ matroids of Tutte, a further $9$ sporadic constraint matroids, and two well-behaved infinite families. Matroids realisable as graphs appear famously in Whitney's planarity criterion: Carmesin proved an extension of Whitney's planarity criterion to the embeddability of local simply connected $2$-complexes into ℝ^3. An application of our theorem is an extension of this theorem beyond the simply connected regime.
ER -