Feladat: Egy konvex n-szög csúcsai alkossák egy egyszerű gráf ponthalmazát. Két pontot kössünk össze, ha kerületi távolságük k (0 < k < n). Legyen H(n,k) az így kapott gráf. Írjuk le az elérhetőség relációt. Milyen n,k értékekre lesz ez a gráf összefüggő?
Feladat: Egy n x k méretű sakktábla mezői alkossák egy egyszerű gráf ponthalmazát. Két mező akkor és csak akkor van összekötve, ha egyikről a másikra a huszár lépni tud. Legyen L(n,k) az így kapott gráf. Írjuk le a gráf elérhetőség relációját. Milyen n,k értékekre lesz ez a gráf összefüggő?
Feladat: Tegyük fel, hogy s és t a G gráf két csúcsa továbbá, s-ből nem érhető el t. Ekkor G csúcsai S és T halmazokra bontható úgy, hogy a s csúcs S eleme legyen, t csúcs T eleme legyen, továbbá S és T közt ne haladjon él (azaz ne legyen olyan s' eleme S és t' eleme T, amelyekre s' és t' összekötött).
Feladat: Bizonyítsuk be, hogy minden G egyszerű gráf esetén G vagy komplementere összefüggő.
Feladat: Bizonyítsuk be, hogy ha egy 2n pontú egyszerű gráf minden foka legalább n, akkor összefüggő.
Feladat: Bizonyítsuk be, hogy ha egy n pontú egyszerű gráfnak legalább (n-12)+1 éle van, akkor összefüggő.
Feladat: Bizonyítsuk be, hogy egy összefüggő gráfból el tudunk hagyni egy pontot úgy, hogy összefüggő maradjon.
Definíció: Legyen G egy összefüggő gráf és x,y két csúcsa. Legyen d(x,y) a legrövidebb xy út hossza. Legyen D(x,y) a leghosszabb xy út hossza.
Feladat: Bizonyítsuk be, hogy a d és D függvények is kielégítik a háromszögegyenlőtlenséget.