Graafin jäykkyys on graafin liitettävyyden mitta : graafi G on t -jäykkä jollekin todelliselle t :lle, jos millä tahansa kokonaisluvulla k > 1 graafia G ei voida jakaa k eri yhdistetyksi komponentiksi poistamalla vähemmän kuin tk pistettä. Esimerkiksi graafi 1 on jäykkä, jos kärkien poistamisesta johtuvien komponenttien määrä ei aina ylitä poistettujen pisteiden määrää. Graafin jäykkyys on maksimi t , jolle se on t -jäykkä. Luku on äärellinen luku kaikille äärellisille kaavioille, lukuun ottamatta täydellisiä kaavioita , joilla on sopimuksen mukaan ääretön jäykkyys.
Vaclav Chvatal esitteli jäykkyyden vuonna 1973 [1] ; Myöhemmin käsitteelle on omistettu paljon muiden graafiteoreetikojen laajaa tutkimusta, esimerkiksi vuoden 2006 katsauksessa [2] , joka on kokonaan omistettu jäykkyydelle, on 99 lausetta ja 162 sivua.
K pisteen poistaminen polkugraafista voi jakaa graafin k + 1 yhdistetyksi komponentiksi. Komponenttien suurin suhde poistettujen kärkien määrään saavutetaan poistamalla yksi kärki (polun sisällä), mikä johtaa polun jakaantumiseen kahdeksi komponentiksi. Näin ollen polut ovat 1⁄2 -kovia . Sitä vastoin k pisteen poistaminen graafisyklistä jättää korkeintaan k yhdistettyä komponenttia ja joskus täsmälleen k yhdistettyä komponenttia, joten sykli on 1 -kova.
Jos graafi on t -jäykkä, saadaan se seuraus (jos laitamme k = 2), että mikä tahansa 2 t − 1 kärjen joukko voidaan poistaa, mutta graafi ei hajoa kahteen osaan. Toisin sanoen mikä tahansa t -jäykkä graafi on kärkeen 2 t - kytketty .
Chvatal [1] huomasi, että mikä tahansa sykli , ja siten mikä tahansa Hamiltonin graafi , on 1 -jäykkä. Eli 1 -jäykkyys on välttämätön ehto sille, että se on Hamiltonin. Chvatal arveli, että jäykkyyden ja Hamiltonin välinen suhde toimii molempiin suuntiin, eli on olemassa kynnys t siten, että mikä tahansa t -jäykkä graafi on Hamiltonin. Alkuoletus Riitti, että t = 2 todistaisi Fleischnerin lauseen , mutta Bauer, Broersma ja Veldman kumosivat oletuksen [3] . Hamiltonisuuden kynnyksen olemassaolo on edelleen avoin ongelma.
Sen tarkistaminen, onko graafi 1 -jäykkä, on co-NP -täydellinen tehtävä . Toisin sanoen ratkaistavuusongelma , johon vastaus "kyllä" tarkoittaa, että graafi ei ole 1-jäykkä ja vastaus "ei" tarkoittaa, että graafi on 1-jäykkä, on NP-täydellinen ongelma. Sama pätee mille tahansa kiinteälle positiiviselle rationaaliluvulle q — sen testaaminen , onko graafi q -jäykkä, on koNP-täydellinen tehtävä [4] .