Bipartite edge frustration of nut graphs: proofs and constructions

@misc{basic2026bipartite,
  title = {{Bipartite edge frustration of nut graphs: proofs and constructions}},
  author = {Nino Bašić and Patrick W. Fowler},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.15679},
  eprint = {2610.15679},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.15679},
}

TY  - UNPB
TI  - Bipartite edge frustration of nut graphs: proofs and constructions
AU  - Nino Bašić
AU  - Patrick W. Fowler
PY  - 2026
DA  - 2026/10/11
PB  - arXiv
DO  - 10.48550/arxiv.2610.15679
UR  - https://arxiv.org/abs/2610.15679
AB  - The bipartite edge frustration of a graph G, φ(G), is the minimum number of edges that must be removed from G to obtain a graph that is bipartite. Core graphs are singular graphs on $2$ or more vertices, for which the kernel of the adjacency matrix contains a full eigenvector. A nut graph is a core graph of nullity one. Nut graphs G are non-bipartite. It is proved here that φ(G) ≥ 2 if G is a nut graph, i.e. every nut graph requires deletion of at least two edges to produce a bipartite graph. In addition, we give a constructive proof that for every integer k ≥ 2 there exist infinitely many chemical nut graphs G with φ(G) = k. Furthermore, for 3 ≤ d ≤ 8, the values k, for which a d-regular nut graph G with φ(G) = k exists, are characterised. It is shown here that for every integer k ≥ 2 there exist infinitely many cubic polyhedral nut graphs G with φ(G) = k. Two ways of producing larger nut graphs from smaller are described: the cut and frustration constructions. One straightforward consequence is that total double subdivision of a nut graph (i.e. simultaneous insertion of two degree-$2$ vertices into every edge) yields a nut graph.
ER  -