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 $\max \{\lceil 2n/(2k-1)\rceil ,k^2-k-2-(k-3)n\}.$ We prove this conjecture.

17 pages