Graph toughness

<h2 id="examples">Examples</h2>
<p>Removing k vertices from a <a href="/facts/Path_graph/4Y2f35eM">path graph</a> can split the remaining graph into as many as <i>k</i> + 1 connected components. The maximum ratio of components to removed vertices is achieved by removing one vertex (from the interior of the path) and splitting it into two components. Therefore, paths are ⁠1/2⁠-tough. In contrast, removing k vertices from a <a href="/facts/Cycle_graph/bYhnPDHc">cycle graph</a> leaves at most k remaining connected components, and sometimes leaves exactly k connected components, so a cycle is 1-tough.
</p>
<h2 id="connection-to-vertex-connectivity">Connection to vertex connectivity</h2>
<p>If a graph is t-tough, then one consequence (obtained by setting <i>k</i> = 2) is that any set of 2<i>t</i> − 1 nodes can be removed without splitting the graph in two. That is, every t-tough graph is also <a href="/facts/K-vertex-connected_graph/EST9uf8W">2<i>t</i>-vertex-connected</a>.
</p>
<h2 id="connection-to-hamiltonicity">Connection to Hamiltonicity</h2>

Unsolved problem in mathematics
Is there a number 
  
    
      
        t
      
    
    {\displaystyle t}
  
 such that every 
  
    
      
        t
      
    
    {\displaystyle t}
  
-tough graph is Hamiltonian?
<a href="/facts/List_of_unsolved_problems_in_mathematics/RroxGPpP">More unsolved problems in mathematics</a>

<p>Chvátal (1973) observed that every <a href="/facts/Cycle_graph/bYhnPDHc">cycle</a>, and therefore every <a href="/facts/Hamiltonian_path/MHjY2xoY">Hamiltonian graph</a>, is 1-tough; that is, being 1-tough is a <a href="/facts/Necessary_condition/G45aDCY9">necessary condition</a> for a graph to be Hamiltonian. He conjectured that the connection between toughness and Hamiltonicity goes in both directions: that there exists a threshold t such that every t-tough graph is Hamiltonian. Chvátal's original conjecture that <i>t</i> = 2 would have proven <a href="/facts/Fleischner%2527s_theorem/GSC1yHnK">Fleischner's theorem</a> but was disproved by Bauer, Broersma & Veldman (2000). The existence of a larger toughness threshold for Hamiltonicity remains open, and is sometimes called Chvátal's toughness conjecture.
</p>
<h2 id="computational-complexity">Computational complexity</h2>
<p>Testing whether a graph is 1-tough is <a href="/facts/Co-NP/M67JgWNa">co-NP</a>-complete. That is, the <a href="/facts/Decision_problem/cQNWjbdE">decision problem</a> whose answer is "yes" for a graph that is not 1-tough, and "no" for a graph that is 1-tough, is <a href="/facts/NP-complete/NFPv56DU">NP-complete</a>. The same is true for any fixed positive <a href="/facts/Rational_number/VJQmyY05">rational number</a> q: testing whether a graph is q-tough is co-NP-complete (Bauer, Hakimi & Schmeichel 1990).
</p>
<h2 id="see-also">See also</h2>
<ul><li><a href="/facts/Strength_of_a_graph/zDSpAjRb">Strength of a graph</a>, an analogous concept for edge deletions</li>
<li><a href="/facts/Tutte%25E2%2580%2593Berge_formula/XhP9JGM2">Tutte–Berge formula</a>, a related characterization of the size of a maximum matching in a graph</li>
<li><a href="/facts/Harris_graph/l1packdy">Harris graphs</a>, a family of graphs that are tough, Eulerian, and non-Hamiltonian</li></ul>

<ul><li>Bauer, Douglas; Broersma, Hajo; Schmeichel, Edward (2006), "Toughness in graphs—a survey", <i><a href="/facts/Graphs_and_Combinatorics/kQJQ9uUy">Graphs and Combinatorics</a></i>, 22 (1): 1–35, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1007%2Fs00373-006-0649-0">10.1007/s00373-006-0649-0</a>, <a href="/facts/MR_(identifier)/uP137L11">MR</a> <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=2221006">2221006</a>, <a href="/facts/S2CID_(identifier)/ldJsHa2Y">S2CID</a> <a href="https://api.semanticscholar.org/CorpusID:3237188">3237188</a>.</li>
<li>Bauer, D.; Broersma, H. J.; Veldman, H. J. (2000), <a href="https://research.utwente.nl/en/publications/not-every-2tough-graph-is-hamiltonian(8189db8b-1470-4c06-b5a2-19d621bfc91b).html">"Not every 2-tough graph is Hamiltonian"</a>, Proceedings of the 5th Twente Workshop on Graphs and Combinatorial Optimization (Enschede, 1997), <i><a href="/facts/Discrete_Applied_Mathematics/0xgV889h">Discrete Applied Mathematics</a></i>, 99 (1–3) (1-3 ed.): 317–321, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1016%2FS0166-218X%2899%2900141-9">10.1016/S0166-218X(99)00141-9</a>, <a href="/facts/MR_(identifier)/uP137L11">MR</a> <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=1743840">1743840</a>.</li>
<li>Bauer, D.; <a href="/facts/S._L._Hakimi/0Dj6cfxl">Hakimi, S. L.</a>; Schmeichel, E. (1990), "Recognizing tough graphs is NP-hard", <i><a href="/facts/Discrete_Applied_Mathematics/0xgV889h">Discrete Applied Mathematics</a></i>, 28 (3): 191–195, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1016%2F0166-218X%2890%2990001-S">10.1016/0166-218X(90)90001-S</a>, <a href="/facts/MR_(identifier)/uP137L11">MR</a> <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=1074858">1074858</a>.</li>
<li><a href="/facts/V%25C3%25A1clav_Chv%25C3%25A1tal/kUQzU5oP">Chvátal, Václav</a> (1973), "Tough graphs and Hamiltonian circuits", <i><a href="/facts/Discrete_Mathematics_(journal)/K4e6z8wQ">Discrete Mathematics</a></i>, 5 (3): 215–228, <a href="/facts/Doi_(identifier)/muM9Etpq">doi</a>:<a href="https://doi.org/10.1016%2F0012-365X%2873%2990138-6">10.1016/0012-365X(73)90138-6</a>, <a href="/facts/MR_(identifier)/uP137L11">MR</a> <a href="https://mathscinet.ams.org/mathscinet-getitem?mr=0316301">0316301</a>.</li></ul>

Graph toughness open-in-new

Graph toughness