---
tag: 3GAP3BZKNJ
kind: concept
name: Graph toughness
sources:
  - wikipedia: en:8839340@r1270701298
    locator: Graph toughness
    note: adopted
    mention: wikipedia://en/8839340
    sections: [Summary]
same_as:
  wikidata: Q5597099
  wikipedia: Graph toughness
inventory: [GRP0V9E1X2]
---

## Summary

In graph theory, **toughness** is a measure of the connectivity of a graph. A graph $G$ is said to be $t$-tough for a given [[real number|08J2M1JYAG]] $t$ if, for every [[integer|0C4JS9RF5M]] $k > 1$, $G$ cannot be split into $k$ different connected components by the removal of fewer than $tk$ vertices. For instance, a graph is $1$-tough if the number of components formed by removing a set of vertices is always at most as large as the number of removed vertices. The toughness of a graph is the maximum $t$ for which it is $t$-tough; this is a finite number for all finite graphs except the [[complete graphs|03WKB2H474]], which by convention have infinite toughness.