Sufficient average degree conditions for the existence of large highly connected subgraphs
Listen
Radio episode about this paper
Transcript
Introduction to the show: ident: Mathematics. The day in mathematics: new theorems, new proofs, and what they open.
Ada: I'm Ada.
Emmy: And I'm Emmy, here with Kolya.
Ada: We're looking at the paper: "Sufficient average degree conditions for the existence of large highly connected subgraphs".
Emmy: Here's the gist of the paper. Sufficient average degree conditions for the existence of large highly connected subgraphs Mader proved that every sufficiently large graph with average degree at least (2 + √2)k has a (k + 1)-connected subgraph He also conjectured that an average degree of at least 3k is sufficient.
Ada: The best known sufficient factor was improved by multiple authors but never reached 3.
Emmy: In the present paper, it is further improved to 3.109 In addition, the obtained (k + 1)-connected subgraph is constrained to have more than 1.2k vertices.
Ada: Moreover, similar conditions on the average degree are proven to be sufficient for the existence of even greater (k + 1)-connected subgraphs.
Title and authors: Ada: We've talked about what this paper is trying to do and some of the improvements they've made regarding the necessary average degree for finding large highly connected subgraphs. Now we want to look at the actual title and who wrote it, "Sufficient average degree conditions for the existence of large highly connected subgraphs."
Emmy: It’s a very direct title. It tells you exactly what this paper is about: connecting graph density, which is measured by average degree, to finding substructures with high connectivity.
Kolya: From an algebraic geometry standpoint, I'm interested in how they frame the problem. Is this purely a counting argument about edges and vertices, or are there deeper structural properties being used that we can see through their math?
Ada: It’s mostly counting, but it relies heavily on defining these specific structures called 2graphs <ref:2511.08256#pg1>. The authors introduce this concept to simplify the edge counting and to get rid of those messy lower order terms that usually plague these kinds of problems.
Emmy: That’s right. They define a 2graph as something with vertices and pairs of edges between them, and they normalize the size using v bar G and e bar G, which are just the number of vertices divided by k and the number of edge pairs divided by k squared <ref:2511.08256#pg1>.
Kolya: So, this transformation into 2graphs seems to be a key methodological move <ref:2511.08256#pg1>. It sounds like it’s a clever way to handle the complexity without getting bogged down in messy calculations involving k itself constantly.
Ada: Precisely. The goal there is to use the structure of these 2graphs, especially when they are sigma separable, to establish bounds on the number of edges relative to the number of vertices <ref:2511.08256#pg1>.
The paper's summary: Emmy: To summarize what this paper actually presents in "Sufficient average degree conditions for the existence of large highly connected subgraphs," it shows that even with these structural modifications, you still need a certain threshold on your average degree to guarantee finding a k plus one connected subgraph.
Ada: The core result they present is Theorem one which lays out three different ways to set up the condition using sigma and delta <ref:2511.08256#pg1>. For instance, you can choose sigma greater than the square root of two plus one over three divided by two, and then delta based on that choice.
Kolya: So they are giving us explicit recipes for setting those parameters instead of just saying "pick a large enough number." That’s useful because it makes the condition more concrete for someone trying to apply it.
Emmy: They also present Theorem two which shows the existence of graphs that fail this condition <ref:2511.08256#pg1>. This theorem proves that if you choose a specific delta, say delta times k minus two, you can still construct arbitrarily large graphs that don't have a k plus one connected subgraph on more than one point two times k vertices.
Ada: And the construction for Theorem two is quite intricate—it involves an inductive process to build these graphs G zero, G one, and so on, where each step adds structure in a very specific way to ensure it avoids the target subgraph <ref:2511.08256#pg1>.
Kolya: That's interesting because the construction itself seems designed precisely to be adversarial against the existence of that connected subgraph. It’s like they are building a graph that is specifically engineered to resist having those high-connectivity pieces.
The paper's improvements: Ada: Now let's talk about the actual improvements this paper suggests over what was known before. They take the original Mader result and push it higher than three point one six times k minus one, reaching three point one zero nine times k minus one.
Emmy: The real structural improvement they highlight is the use of sigma-separability to strengthen Theorem one into Theorem four <ref:2511.08256#pg1>. This involves a concept called sigma-separability, which allows them to establish bounds for edge numbers based on how separable the 2graph is <ref:2511.08256#pg1>.
Kolya: So, when you look at this strengthening with sigma-separability, what does that imply about the complexity of proving these existence theorems? Does it make them easier or harder?
Ada: It makes the proof method more robust because Theorem four uses this separability concept to generalize Theorem one <ref:2511.08256#pg1>. It shows that if you have a certain property on every sigma separable 2graph, you get a much better guarantee about the average degree needed <ref:2511.08256#pg1>.
Emmy: They even introduce Lemma one which says that if every sigma separable 2graph has an edge count less than delta times the vertex count, then any graph with average degree at least delta times k minus one will have that large highly connected subgraph <ref:2511.08256#pg1,graph with average degree at least>.
Kolya: That sounds like a nice way to generalize the result beyond just the specific cases they studied. It moves it from being case-specific to being dependent on a broader structural property of the entire graph structure.
Conclusion: Ada: So, wrapping up on "Sufficient average degree conditions for the existence of large highly connected subgraphs," we’ve seen how the paper refines Mader's result and introduces new tools like 2graphs and sigma-separability to tighten the bounds <ref:2511.08256#pg1,Sufficient average degree conditions for the existence of large highly connected subgraphs>.
Emmy: The main implication is that we have a more precise threshold, three point one zero nine times k minus one, for finding these kinds of subgraphs, with a size constraint of at least one point two times k vertices.
Kolya: I just want to weigh in on the construction idea from Theorem two—that inductive building process <ref:2511.08256#pg1>. It seems very technical and specialized for proving that a counterexample can exist when the average degree is just below the required threshold.
Ada: Exactly, it is highly specialized, but it’s necessary to show that we can indeed construct graphs that defy the condition when you're slightly under the average degree requirement. That kind of detail shows where the limits of our current understanding lie.
Emmy: And I think the use of 2graphs really helps bridge that gap between pure counting and a more structural argument, allowing them to analyze these properties in a way that is both rigorous and manageable for this type of problem <ref:2511.08256#pg1>.
Kolya: So, if you take everything we've discussed—the improvements to the average degree factor, the new structural tools—what does this paper tell us about where we should focus our attention next?
Ada: I think the main challenge moving forward is proving that Theorem one part one is true for all sigma greater than one <ref:2511.08256#pg1>. That would mean finding a condition that doesn't rely on those specific choices of sigma and delta anymore.
Emmy: And if they can do that, then the factor three in Mader's conjecture starts to look much more attainable with this approach.
Kolya: For me, I’m interested in seeing how these new bounds interact with other problems, like those about large deviations or dimension-free bounds on Poincaré constants. It would show if this methodology is a general tool across different areas of combinatorics.
Ada: That sounds like a great direction for future research. So that's our take on "Sufficient average degree conditions for the existence of large highly connected subgraphs."
Maximilian Krone
Technische Universität Ilmenau
math.CO
Submitted: 2025-11-11
Updated: 2026-11-10
Comments: New version: Theorem 1(1) has been extended, a generalization of high connectivity and order has been studied, and the structure of all proofs has been revised
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Importance score: 76/100
The gist: Sufficient average degree conditions for the existence of large highly connected subgraphs Mader proved that every sufficiently large graph with average degree at least (2 + √2)k has a (k +…
Key concepts
- Average Degree
- This measures how many connections, on average, each vertex in a graph has. The paper uses this value to determine if a graph is dense enough to guarantee the existence of large subgraphs with high connectivity, like (k+1)-connectivity.
- 2graph
- A 2graph is a mathematical structure used to simplify edge counting in graphs. It treats edges as pairs of vertices, allowing for parallel edges and loops. This transformation helps in analyzing complex connectivity properties by using normalized quantities like v̄(G) and ē(G).
- Sigma-separability
- This is a property applied to 2graphs that helps in proving structural bounds. If every 'sigma-separable' 2graph satisfies a certain edge density condition, it allows the authors to establish sufficient conditions for finding highly connected subgraphs.
- (k+1)-connected subgraph
- A graph is (k+1)-connected if you need to remove at least k+1 vertices to disconnect it. The paper focuses on proving that graphs with a sufficiently high average degree possess such large, highly connected structures.
Terminology
Summary
Sufficient average degree conditions for the existence of large highly connected subgraphs Mader proved that every sufficiently large graph with average degree at least (2 + √2)k has a (k + 1)-connected subgraph He also conjectured that an average degree of at least 3k is sufficient. p. 0 The best known sufficient factor was improved by multiple authors but never reached 3. p. 0 p. 0 In the present paper, it is further improved to 3. p. 0 p. 0109 In addition, the obtained (k + 1)-connected subgraph is constrained to have more than 1. p. 0 p. 02k vertices. p. 0 p. 0 Moreover, similar conditions on the average degree are proven to be sufficient for the existence of even greater (k + 1)-connected subgraphs. p. 0 p. 0
Key Theorems and Conditions
Theorem 1 establishes sufficient conditions for finding a (k + 1)-connected subgraph on more than (1 + σ)k vertices based on average degree It presents three alternatives for choosing σ and δ:
(1) σ ≥ √√2+1/3 ≈ 1.394 and δ = 2 + σ + 1/3σ. p. 0
(2) σ = 1/3q 5/2 > 0.527 and δ = 2 + 11/3q 1/10. p. 0
(3) σ = 0.2 and δ = 3.109.
In particular, every graph with average degree at least 3. p. 0109 k − 1 has a (k + 1)-connected subgraph. p. 0
Theorem 2 demonstrates the existence of arbitrary large graphs with average degree greater than δk−2 without a (k+1)-connected subgraph on more than (1+σ)k vertices. p. 1 The proof involves an inductive construction of graphs G0, G1,. p. 1..
Structural Modifications for Proof
The authors introduce a modification of the edge number using 2graphs to simplify counting and remove lower order terms. A 2graph is defined as a pair G = V (G), E(G) with E(G) ⊆ V (G)2 = V (G) × V (G). p. 2 Normalization involves v¯(G):= v(G)/k and e¯(G):= e(E(G))/k squared.
Strengthening via Separability
Theorem 4 provides a general strengthening of Theorem 1 using the concept of σ-separability. Lemma 1 states that if every σ-separable 2graph G with v¯(G) ≥ δ satisfies e¯(G) < δ v¯(G), then every graph with average degree at least δk − 1 has a (k + 1)-connected subgraph on more than (1 + σ)k vertices. p. 2 Theorem 3 applies this to the case where σ ≥ √1/2 and δ = 2 + σ + 1/2σ. p. 9
Complexity of the Proof
The proof of Theorem 4 is done inductively on the vertex number of the 2graph G. The base case for Theorem 4 (3) involves complex optimization problems using Lemma 3 and leads to intricate bounds involving various parameters like r(G). p. 6 The outlook suggests that proving the factor 3. p. 0108 demands new ideas because the current approach struggles with the factor 3. p. 0
Conclusion and Outlook
The authors believe to be able to prove Carmesin’s statement [4], that is Theorem 1 (1) for all σ ≥ 1. This proof would contain some very specific arguments that might not allow nice generalizations. p. 0 The outlook indicates that the factor 3, which appears in Mader’s conjecture [2], seems inaccessible with the presented approach. p. 0 The author believes to be able to prove Carmesin’s statement [4], that is Theorem 1 (1) for all σ ≥ 1. p. 0 The proof of Theorem 4 (3) concludes by showing that the desired upper bound is achieved if and only if certain conditions are met in the proposed case. p. 9
References
[1] W. Mader (1972). p. 0 Existenz n-fach zusammenhängender Teilgraphen in Graphen genügend großer Kantendichte. Abhandlungen aus dem math. p. 0 Seminar der Universität Hamburg, 37, 86-97
[2] W. Mader (1979). p. 0 Connectivity and edge-connectivity in finite graphs. p. 1 in: B. Bollobás (Ed.), Surveys in Combinatorics, Cambridge University Press, 66–95
[3] A. Bernshteyn, A. p. 0 Kostochka (2016). p. 0 On the number of edges in a graph with no (k+1)-connected subgraphs. p. 0 Discrete Mathematics, 339(2), 682–688
[4] J. Carmesin (2020+). p. 0 Large highly connected subgraphs in graphs with linear average degree. p. 0 Preprint. https://arxiv. p. 0 p. 0org/abs/2003.00942
[5] W. Mader (1971). p. 0 Minimale n-fach kantenzusammenhängende Graphen. Mathematische Annalen, 191, 21–28
[6] M. Krone (2025+). p. 0 Sufficient minimum degree conditions for the existence of highly connected or edge-connected subgraphs. p. 0 Preprint. https://arxiv.org/abs/2508.07997
--- Page 1 ---
Sufficient average degree conditions for the existence of large highly connected subgraphs Mader proved that every sufficiently large graph with average degree at least (2 + √2)k has a (k + 1)-connected subgraph He also conjectured that an average degree of at least 3k is sufficient. The best known sufficient factor was improved by multiple authors but never reached 3. In the present paper, it is further improved to 3.109 In addition, the obtained (k + 1)-connected subgraph is constrained to have more than 1.2k vertices. Moreover, similar conditions on the average degree are proven to be sufficient for the existence of even greater (k + 1)-connected subgraphs.
--- Page 2 ---
Theorem 1 (1) might also be true for all σ ≥ 1, which is indicated by Carmesin [4] The value of δ would then be best possible for k → ∞:
--- Page 3 ---
Theorem 2 Let σ ≥ 1 with σk ∈ N and δ = 2 + σ + 1/3σ. There exist arbitrary large graphs with average degree greater than δk−2 without a (k+1)-connected subgraph on more than (1+σ)k vertices Proof. p. 1 The idea for the construction is due to Carmesin [4]. p. 1 We inductively construct G0, G1,. p. 1.. with the following properties:
--- Page 4 ---
(i) Gi has no (k + 1)-connected subgraph on more than (1+σ)k vertices.
(ii) v(Gi − k) = 2iσk. p. 1
(iii) Gi contains a set Xi of 2k vertices that is a disjoint union of 2 i (potentially empty) vertex sets whose size differs by at most 1 such that there is no edge between each two of these sets. p. 1
(iv) e(Gi) ≥ 2 i((1+σ)k) squared / (3 - 4-i k 2).
--- Page 5 ---
Let G0 be the complete graph on (1 + σ)k vertices, which clearly satisfies (i), (ii) and also (iii) since σ ≥ 1 We have that e(G0) = (1+σ)k squared / 2. Now assume we have already constructed Gi, and we want to construct Gi+1. p. 1 We can partition the set Xi from (iii) into a set Yi and Zi, each of k vertices, that inherit the property of Xi: both of them are a disjoint union of 2 i vertex sets whose size differs by at most 1 such that there is no edge between each two of these sets. p. 1 The number of edges e(Yi) between the vertices of Yi is at most 2(-i k 2). p. 1
--- Page 6 ---
We construct Gi+1 by taking two copies of Gi, that intersect exactly in the set Yi of k vertices. Since Gi contains no (k + 1)-connected subgraph on more than (1 + σ)k vertices, neither Gi+1 does. p. 1 Clearly, v(Gi+1) − k = 2(v(Gi − k)) = 2i+σk. p. 1 We obtain the set Xi+1 from the union of both copies of Zi. p. 1 For (iv), e(Gi+1) = 2e(Gi) - e(Yi) ≥ 2 i((1+σ)k) squared / (3 - 4-i k 2) - 2(-i k 2).
--- Page 7 ---
This finishes the induction. We further bound 2e(Gi) ≥ 2(i+1)((1+σ)k) squared / (3 - 4-i k 2) - e(Yi). p. 1 This yields 2e(Gi)/v(Gi − k) ≥ σ + 2 + 1/3σ k − 1/3σ. p. 1
--- Page 8 ---
A modification of the edge number The idea for a useful strengthening of Theorem 1 first leads to quite ugly expressions. Fortunately, those get a lot nicer if we change the way we count the edges. p. 2 A graphic interpretation of the counting are special multigraphs. p. 2 In particular, this approach allows to get rid of lower order terms and also of the parameter k, which only hides in the definitions:
--- Page 9 ---
• A 2graph is a pair G = V (G), E(G) with E(G) ⊆ V (G)2 = V (G) × V (G). We do not need to think of directed edges. p. 2 Instead, a 2graph can be seen as a multigraph, in which pairs of parallel edges and single loops per vertex are allowed. p. 2
• Let k ∈ N be fixed throughout the whole paper. p. 2 For a graph or 2graph G, we normalize v¯(G):= v(G)/k and e¯(G):= e(E(G))/k squared. p. 2 Hence, for every 2graph G we have e¯(G) ≤ v¯(G) squared with equality if and only if E(G) = V (G)2. p. 2
• A 2graph C is called a sub2graph of a 2graph G if V (C) ⊆ V (G) and E(C) ⊆ E(G). p. 2
• C is called spanning if V (C) = V (G). p. 2
• C is called induced (by V (C)) if E(C) = E(G)V (C)2. p. 2
• A separation of a 2graph G is a pair (A, B) of induced but not spanning sub2graphs A and B with V (A) ∪ V (B) = V (G), E(A) ∪ E(G) = E(G) and v¯V (A)∩V (B)=1. p. 2
• We set B > A:= V (B), E(B − A). p. 1 B − A contains the induced sub2graph A ⊓ B:= V (A) ∩ V (B), empty edge-set (which we call an anticlique). p. 2 p. 2
--- Page 10 ---
We set B - A:= V (B), E(B − A). B − A contains the induced sub2graph A ⊓ B:= V (A) ∩ V (B), empty edge-set (which we call an anticlique).
--- Page 11 ---
A separation of a 2graph G is a pair (A, B) of induced but not spanning sub2graphs A and B with V (A) ∪ V (B) = V (G), E(A) ∪ E(G) = E(G) and v¯V (A)∩V (B)=1.
--- Page 12 ---
We set B > A:= V (B), E(B − A). B − A contains the induced sub2graph A ⊓ B:= V (A) ∩ V (G), empty edge-set (which we call an anticlique). p. 2
--- Page 13 ---
The derivative of this expression in a is 2 times −1/(1 + s)(g − a) + 1/2a squared + 1/4a 4 + 1/0.34a 4−0.2
--- Page 8 ---
A separation of a 2graph G is a pair (A, B) of induced but not spanning sub2graphs A and B with V (A) ∪ V (B) = V (G), E(A) ∪ E(G) = E(G) and v¯V (A)∩V(B)=1
--- Page 9 ---
We set B > A:= V (B), E(B − A). B − A contains the induced sub2graph A ⊓ B:= V (A) ∩ V (G), empty edge-set (which we call an anticlique)
--- Page 10 ---
We set B - A:= V (B), E(B − A). B - A contains the induced sub2graph A ⊓ B:= V (A) ∩ V(G), empty edge-set (which we call an anticlique)
--- Page 11 ---
A separation of a 2graph G is a pair (A, B) of induced but not spanning sub2graphs A and B with V (A) ∪ V (B) = V (G), E(A) ∪ E(G) = E(G) and v¯V (A)∩V(B)=1
--- Page 12 ---
We set B > A:= V (B), E(B − A). B − A contains the induced sub2graph A ⊓ B:= V (A) ∩ V(G), empty edge-set (which we call an anticlique)
--- Page 8 ---
A separation of a 2graph G is a pair (A, B) of induced but not spanning sub2graphs A and B with V (A) ∪ V(B) = V(G), E(A) ∪ E(G) = E(G) and v¯V (A)∩V(B)=1
--- Page 9 ---
We set B > A:= V (B), E(B − A). B − A contains the induced sub2graph A ⊓ B:= V(A) ∩ V(G), empty edge-set (which we call an anticlique)
--- Page 10 ---
We set B - A:= V (B), E(B − A). B - A contains the induced sub2graph A ⊓ B:= V(A) ∩ V(G), empty edge-set (which we call an anticlique)
--- Page 11 ---
A separation of a 2graph G is a pair (A, B) of induced but not spanning sub2graphs A and B with V(A) ∪ V(B) = V(G), E(A) ∪ E(G) = E(G) and v¯V (A)∩V(B)=1
--- Page 12 ---
We set B > A:= V (B), E(B − A). B - A contains the induced sub2graph A ⊓ B:= V(A) ∩ V(G), empty edge-set (which we call an anticlique)
--- Page 8 ---
A separation of a 2graph G is a pair (A, B) of induced but not spanning sub2graphs A and B with V(A) ∪ V(B) = V(G), E(A) ∪ E(G) = E(G) and v¯V (A)∩V(B)=1
Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.
Improvements for AI systems
-
Improved subgraph detection based on average degree can guarantee finding a (k+1)-connected subgraph on more than (1 + sigma)k vertices if the average degree is at least delta k minus 1, where delta is chosen according to specific structural parameters sigma and a function of sigma.
-
The system can utilize the transformation into a 2graph setting to analyze graph connectivity properties using edge counting, specifically leveraging the bound e bar G less than delta v bar G for σ separable 2graphs.
-
The AI system can apply Theorem 4 to find a spanning sub2graph with arbitrary disjoint anticliques, yielding an upper bound on the edge number e bar G' that accounts for these structures through the term x l i=1 v bar Gi 2.
-
The system can employ Lemma 5 to establish bounds for e bar G when G is sigma separable and contains disjoint anticliques, providing a more generalized result than needed for specific cases in Theorem 4 (2).
-
The AI system can use the optimization problem described in Lemma 3 to determine the maximum value of an expression involving x and z minus x subject to constraints, which helps in deriving tighter bounds for edge numbers.
Sources
- Large highly connected subgraphs in graphs with linear average degree
- Sufficient minimum degree conditions for the existence of highly connected or edge-connected subgraphs
Related papers
- Three-ends Furstenberg estimates and approximate rectangles
- Multicolor Ramsey numbers of ordered matchings
- Exponential random graph models with soft clique constraints
- A Full-Sequence Quantitative Gap Between the Chromatic and Cochromatic Numbers of a Random Graph
- Ehrhart positivity for paving positroids
- Nonlinear lower-tail large deviations at criticality