{"id":"arxiv/2607.18964","url":"https://arxiv.org/abs/2607.18964","tags":["math.CO"],"score":0,"title":"$k$-Connected Subgraphs of All Orders in Large Graphs with Minimum Degree at Least $n/q$","domain":"math.CO","source":"arxiv","authors":["Heng Yang"],"reviews":0,"subject":"math.CO","summary":"For every fixed pair of integers $k\\ge 2$ and $q\\ge 3$, we prove that every sufficiently large $k$-connected graph $G$ of order $n$ with minimum degree $δ(G)\\ge n/q$ contains a $k$-connected subgraph of every order $\\ell\\in\\{2k,2k+1,\\ldots,n\\}$. In the case $k=2$, this confirms a conjecture of Liu and Ning~\\cite{LiuNing}. The proof combines two constructions. First, we construct a small $k$-connected subgraph $D$ such that every vertex outside $D$ has at least $k$ neighbors in $D$. By successively adding the vertices outside $D$, we obtain $k$-connected subgraphs of every order from $|V(D)|$…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-07-21","reactions":{}}