Kāds ir mazākais skaits šķautņu, kas jāpievieno grafam, lai tas kļūtu sakarīgs (vai k-connected - katras divas virsotnes savienotas ar k ceļiem bez kopīgām virsotnēm) vai tajā rastos Eilera cikls. Arī otrādi - kāds mazākais skaits šķautņu, kas jāpārgriež, lai grafā nebūtu nepāra ciklu, lai tas kļūtu divdaļīgs.