wiki_research

commit 5b4459b4335bf44ea26145e9bcea90a6fe7d01f3
parent 3bc316a100322fd29f975c74670890ffabc401e1
Author: Antoine Amarilli <a3nm@a3nm.net>
Date:   Tue, 18 Aug 2026 18:06:56 +0200

commit with codex

Diffstat:
fleischners_theorem
 | 
5
+++++
graph
 | 
1
+
graph_biconnected
 | 
2
+-
graph_theorem
 | 
1
+
hamiltonian_cycle_square
 | 
2
++
toughness
 | 
19
+++++++++++++++++++

6 files changed, 29 insertions(+), 1 deletion(-)
diff --git a/fleischners_theorem b/fleischners_theorem
@@ -0,0 +1,5 @@
+# Fleischner's theorem
+
+https://en.wikipedia.org/wiki/Fleischner%27s_theorem
+
+Up: [graph_theorem], [hamiltonian_cycle_square]
diff --git a/graph b/graph
@@ -10,6 +10,7 @@ See [graph_basic_notions]
 
 - [graph_minor]
   - [robertson_seymour]
+- [toughness]
 
 ## Types
 
diff --git a/graph_biconnected b/graph_biconnected
@@ -4,6 +4,6 @@ A *biconnected graph* is an [undirected_graph] which is [connected] and has no [
 
 Up: [graph_basic_notions]
 
-Aliases: biconnected graph, biconnected graphs
+Aliases: biconnected graph, biconnected graphs, 2-vertex connected graph, 2-vertex connected graphs, 2-vertex connected, 2 vertex connected, 2 vertex connected graph, 2 vertex connected graphs
 
 See also: [biconnected_component], [block_cut_tree]
diff --git a/graph_theorem b/graph_theorem
@@ -6,6 +6,7 @@
 - [123_conjecture]
 - [friendship_theorem]
 - [handshaking_lemma]
+- [Fleischner's_theorem]
 
 Up: [graph], [theorems]
 
diff --git a/hamiltonian_cycle_square b/hamiltonian_cycle_square
@@ -3,6 +3,8 @@
 On [graphs], it is [NP_hard] to determine if the [graph_square] of an input [graph] is [hamiltonian]
 - cf https://en.wikipedia.org/wiki/Graph_power#Computational_complexity 
 
+However, in a graph is [biconnected], then its [graph_square] is always [hamiltonian]: this is [Fleischner's_theorem]
+
 On [trees], see [radoszewski2011hamiltonian]
 
 Up: [hamiltonian_cycle], [graph_square]
diff --git a/toughness b/toughness
@@ -0,0 +1,19 @@
+# Toughness
+
+https://en.wikipedia.org/wiki/Graph_toughness
+
+A [graph] G is *t-tough* if, for every integer k>1, you must remove at least tk vertices to split G into at least k [connected_components]
+
+Every [Hamiltonian_graph] is 1-tough:
+https://en.wikipedia.org/wiki/Graph_toughness#Connection_to_Hamiltonicity
+but the converse is false
+
+It is [coNP_complete] to test whether a graph is 1-tough, and the same holds for t-toughness for any positive rational number t, cf https://en.wikipedia.org/wiki/Graph_toughness#Computational_complexity
+
+[Chvátal's_toughness_conjecture]
+
+Up: [graph]
+
+See also: [graph_strength]
+
+Aliases: graph toughness