Próbáljuk meg kitalálni, hogy mely gráfok izomorfak egymással.
a)
b)
c)
Nézzük meg, hogy síkbarajzolható-e.
a) Döntsük el, hogy síkbarajzolható-e. Ha igen, rajzoljuk síkba.
b) Döntsük el, hogy síkbarajzolható-e. Ha igen, rajzoljuk síkba.
c) Legalább hány élt kell törölnünk ebből a gráfból, hogy a megmaradt gráf síkbarajzolható legyen?
A következő gráfok közül melyek izomorfak?
a)
b)
c)
A következő gráfok közül melyek izomorfak?
a)
b)
a) Maximálisan hány élt lehet hozzávenni az alábbi gráfhoz úgy, hogy egyszerű, síkbarajzolható gráfot kapjunk?
b) Síkbarajzolható-e az alábbi gráf? Ha igen, rajzoljuk le síkba úgy, hogy az élei egyenes szakaszok legyenek, ha nem, akkor bizonyítsuk be ezt.
c) Síkbarajzolhatók-e az alábbi gráfok?
d) Síkbarajzolhatók-e az alábbi gráfok?
e) Síkbarajzolható-e az alábbi gráf?
A következő gráfok közül melyek izomorfak?
a)
b)
A következő gráfok közül melyek izomorfak?
A következő gráfok közül melyek izomorfak?
Döntsük el, hogy síkbarajzolható-e.
Ha igen, rajzoljuk síkba.
a)
b)
c)
Döntsük el, hogy az alábbi gráfok síkbarajzolhatók-e.
a)
b)
c)
A következő gráfok közül melyek izomorfak?
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.
a) Egy 100 pontú gráfról tudjuk, hogy 50 csúcs mindegyikének a foka legfeljebb 7 a másik 50 csúcs foka pedig legalább 56. Hány éle van ennek a gráfnak?
b) Egy konferencián 60-an vesznek részt. A résztvevők közül 20-an már legalább 27 emberrel kezetfogtak, a többiek pedig még csak legfeljebb 4 emberrel. Hány kézfogás történt eddig?
c) Bizonyítsuk be, hogy egy G gráf és a komplementere közül legalább az egyik összefügő.
a) Bizonyítsuk be, hogy minden egyszerű, síkbarajzolható gráfban van olyan csúcs, melynek foka legfeljebb 5.
b) Legyen G egy 13 pontú egyszerű gráf. Bizonyítsuk be, hogy G és a komplementere közül legalább az egyik nem síkbarajzolható.
c) Létezik-e olyan 4, 5, illetve 6 csúcsú gráf, amely izomorf a saját komplementerével?
d) Az 1000 csúcsú G gráf nem tartalmaz kört, a komponenseinek száma 8. Hány éle van G-nek?
e) Egy fában csak két különböző fokszám fordul elő: az egyik fajta 7-szer, a másik 44-szer. Mi a szóban forgó két fokszám?
a) Hány csúcsa van egy síkbarajzolható 3-reguláris gráfnak, ha a síkbarajzolás során 20 tartomány keletkezik?
b) Egy versenyre 6 különböző országból érkeztek versenyzők. Bizonyítsuk be, hogy van köztük két olyan versenyző, akiknek az országa nem határos egymással.
c) Egy versenyre különböző országból érkeztek versenyzők. Legfeljebb hány országból indulhattak a versenyzők, ha bármelyik két versenyző szomszédos országból érkezett?
d) Egy 20 csúcsú, 3 komponensű gráfnak 18 éle van. Mutassuk meg, hogy a komponensek közül pontosan kettő fa.
e) Egy 100 csúcsú egyszerű gráfban minden pont foka legalább 33. Mutassuk meg, hogy a gráfhoz hozzá lehet venni egyetlen új élt úgy, hogy a kapott gráf összefüggő legyen.
f) Mutassuk meg, hogy minden összefüggő gráfban van olyan csúcs, melyet a gráfból elhagyva (az összes rá illeszkedő éllel együtt) összefüggő gráfot kapunk.
g) Rajzoljuk le az összes 3, 4, illetve 5 pontú fát. (Az izomorfakat csak egyszer)
