Critical Subgraphs of a Random Graph
Abstract
We prove that the threshold for a random graph to have a $k$-core is equal to the threshold for having a subgraph which meets a necessary condition of Gallai for being $k$-critical.
We prove that the threshold for a random graph to have a $k$-core is equal to the threshold for having a subgraph which meets a necessary condition of Gallai for being $k$-critical.