Egy gráf komplementere azt a gráfot jelenti, aminek csúcsai ugyanazok, mint az eredeti gráfnak, és két csúcs pontosan akkor szomszédos benne, ha az eredeti gráfban nem.
Egy gráf komplementere azt a gráfot jelenti, aminek csúcsai ugyanazok, mint az eredeti gráfnak, és két csúcs pontosan akkor szomszédos benne, ha az eredeti gráfban nem.
a) Egy 24 csúcsú G egyszerű gráfban 12 csúcs foka 5, a másik 12 csúcs foka pedig 16. Összefüggő-e a G gráf komplementere?
b) Egy összefüggő egyszerű gráfnak 40 csúcsa és 42 éle van. Bizonyítsuk be, hogy van a gráfban 3 különböző kör. Két kör akkor különböző, ha van legalább egy olyan él, amelyiket az egyik kör tartalmazza, de a másik nem.
c) Egy összefüggő egyszerű gráfnak 1000 csúcsa és 1000 éle van. Bizonyítsuk be, hogy van a gráfban 3 különböző feszítőfa. Két feszítőfa akkor különböző, ha van legalább egy olyan él, amelyiket az egyik feszítőfa tartalmazza, de a másik nem.
