October 16, 2025Open Access

Sufficient minimum degree conditions for the existence of highly connected or edge-connected subgraphs

View Full Paper

Ask AI

Bookmark

Authors

Discussion

Theoretical proof shows average degree conditions for connected and edge-connected subgraphs.

Every graph with minimum degree at least 3k-1 has a (k+1)-connected subgraph on more than 2k vertices.
In triangle-free graphs, an average degree of at least 2k suffices for a (k+1)-connected subgraph with at least 2(k+1) vertices.
Graphs with average degree at least 2k can have a (k+1)-edge-connected subgraph exceeding 2k vertices.
Sharpness of these conditions indicates potential applications for graph decomposition into highly connected parts.

Maximilian Krone (2025) studied this question.

View Full Paper

Ask AI

Bookmark