A proof of Bickle's conjecture on collapsible graphs

Abstract

A graph $G$ is said to be $k$-collapsible if $G$ has minimum degree $k$ and every non-null proper induced subgraph of $G$ has minimum degree less than $k.$ In 2018, Bickle conjectured that the minimum number of vertices of degree $k$ in a $k$-collapsible graph of order $n$ with $k\ge 3$ is ${\rm max}\{\lceil 2n/(2k-1)\rceil,\, k^2-k-2-(k-3)n\}.$ We prove this conjecture.

Disclosure

“− v is (k − 1)-degenerate for every v ∈ V (G). Lemma 3 shows that G is k-collapsible. Finally, s = M (k, n), so G has the required number of bottom vertices. 2 Declaration of AI Use ChatGPT was used to assist in developing and checking the constructions and proofs. The author independently verified all mathematical arguments, wrote the paper, and takes full responsibility for its content.”

PDF page 16

Classification

Proof ideas or individual proof-step assistance

Multiplier

8

Verified

2026-08-23T05:17:46.653003Z

Structural counts