1
Hány éle van egy 15 csúcsú fának?
Egy $n$ csúcsú fának az alaptételek szerint mindig $n-1$ éle van. Egy 15 csúcsú fának ez alapján 14 éle van.
2
Milyen hosszúságú körök nem szerepelhetnek egy páros gráfban?
Páros gráfban nem szerepelhet páratlan hosszúságú kör a Kőnig-tétel értelmében. Egy gráf pontosan akkor páros, ha nem tartalmaz páratlan kört.
3
Egy fának 10 csúcsa van, melyek közül 4 darab harmadfokú, a többi pedig elsőfokú. Hány éle van a gráfnak, és lehetséges-e ilyen fa?
A fokszámösszeg $4 \times 3 + 6 \times 1 = 18$. Az élek száma a fokszámösszeg fele, vagyis 9. Mivel a csúcsok száma 10, a szükséges élszám a fákra vonatkozó tétel alapján $10-1=9$. Ilyen fa megalkotható.
4
Legfeljebb hány éle lehet egy 10 csúcsú páros gráfnak, ha nem tartalmaz többszörös élt?
A csúcsokat két partícióra osztjuk, legyen az elemek száma $k$ és $10-k$. Az élek száma legfeljebb $k(10-k)$. Ez a másodfokú kifejezés $k=5$ esetén veszi fel a maximumát, ami $5 \times 5 = 25$ él.
5
Bizonyítsa be, hogy minden legalább 2 csúcsú fának van legalább két elsőfokú csúcsa.
Egy $n \ge 2$ csúcsú fa éleinek száma $n-1$, így a fokszámösszeg $2(n-1) = 2n-2$. Ha legfeljebb egy elsőfokú csúcs lenne, akkor a többi $n-1$ csúcs legalább másodfokú lenne. Ekkor a fokszámösszeg legalább $1 + 2(n-1) = 2n-1$ adódna, ami ellentmond a $2n-2$-nek. Ebből következik, hogy legalább két elsőfokú csúcs (levél) szükséges.
6
Egy 8 csúcsú összefüggő gráfnak 12 éle van. Legalább hány élt kell elhagyni belőle, hogy feszítőfát kapjunk?
Bármely 8 csúcsú feszítőfának $8-1=7$ éle van. Az eredeti 12 élből tehát pontosan $12-7=5$ élt kell eltávolítani a körmentesítéshez úgy, hogy az összefüggőség megmaradjon.
7
Egy gráf csúcsai a normál sakktábla mezői, és két csúcs között akkor van él, ha a nekik megfelelő mezőkön álló huszárok üthetik egymást. Páros-e ez a gráf?
Igen, a gráf páros. A huszár a szabályos lépése során mindig ellentétes színű mezőre érkezik. A sötét és világos mezők halmaza így két olyan diszjunkt, független halmazt alkot, amelyek között futnak az élek.
8
Lehet-e egy fa csúcsainak fokszámsorozata 4, 3, 3, 2, 2, 1, 1, 1, 1, 1, 1?
A csúcsok száma 11, ezért az élek számának 10-nek kell lennie. A megadott fokszámösszeg $4+3+3+2+2+6 \times 1 = 20$. A fokszámösszeg fele 10, ami megegyezik a szükséges élszámmal. Mivel elegendő levél van a belső csúcsokhoz, a fokszámsorozat megvalósítható egy fával.
9
Adott egy 6 csúcsú gráf, melynek élei a következők: {1,2}, {2,3}, {3,4}, {4,5}, {5,6}, {6,1}. Páros-e ez a gráf?
A megadott élhalmaz egy 6 élből álló, összefüggő kört határoz meg. Mivel a gráf kizárólag egy páros hosszú kört tartalmaz, és nincs benne páratlan hosszúságú kör, a gráf páros.
10
Hány feszítőfája van a $K_{2,3}$ teljes páros gráfnak?
A teljes páros gráf $K_{m,n}$ feszítőfáinak száma az általános képlet alapján $m^{n-1}n^{m-1}$. A paramétereket behelyettesítve $2^{3-1} \cdot 3^{2-1} = 2^2 \cdot 3^1 = 12$ feszítőfa létezik.
11
Hány nem izomorf fa létezik pontosan 5 csúcson?
Összesen 3 darab nem izomorf fa létezik 5 csúcson. Ezek a csillaggráf ($K_{1,4}$), az útgráf ($P_5$), és egy gráf, amelyben egy harmadfokú csúcshoz csatlakozik két levél és egy két él hosszú út.
12
Egy összefüggő páros gráfban az A és B partíciók között húzódnak az élek. Milyen paritású egy A-beli csúcsból egy másik A-beli csúcsba vezető séta hossza?
Minden egyes lépés az egyik partícióból a másikba vezet. Ahhoz, hogy az A partícióból elindulva az A partícióba érkezzünk meg, páros számú él mentén kell áthaladni, így a séta hossza mindig páros.
13
Egy gráfnak 7 csúcsa van, és minden csúcsának fokszáma legfeljebb 3. Hány éle lehet maximálisan, ha a gráf egy fa?
Ha a gráf fa és 7 csúcsa van, akkor a belső szerkezetétől függetlenül pontosan $7 - 1 = 6$ éle van. A fokszámokra vonatkozó feltétel csupán a fa lehetséges elágazásait korlátozza, az élek számát nem befolyásolja.
14
Egy $n$ csúcsú, $k$ komponensből álló körmentes gráfot (erdőt) hány él alkot?
Minden egyes komponens önmagában egy fa. Ha az $i$-edik komponens $n_i$ csúccsal rendelkezik, akkor az éleinek száma $n_i - 1$. Az összes él száma az $(n_i - 1)$ értékek összege, ami egyenlő $n - k$ értékkel.
15
Lehet-e egy 7 csúcsú páros gráf komplementere is páros gráf?
Nem lehet. A Ramsey-tétel értelmében bármely 6 vagy annál több csúcsú gráf, vagy annak komplementere tartalmaz háromszöget. A háromszög egy páratlan kör ($C_3$), így a gráf és komplementere nem lehet egyszerre páros gráf.
16
Igaz-e, hogy minden $n \ge 3$ csúcsú fában van legalább egy olyan csúcs, amelynek eltávolítása után a megmaradó gráf szétesik?
Igen, igaz. Bármely legalább 3 csúcsú fában lennie kell egy olyan belső csúcsnak, amelynek foka legalább 2. Mivel a gráf körmentes, ezen csúcs eltávolításával a szomszédai közötti egyetlen útvonal megszakad, és a gráf különálló komponensekre esik szét.
17
Egy 100 csúcsú gráf 199 élt tartalmaz. Bizonyítható-e ebből, hogy a gráf tartalmaz páratlan kört?
Nem bizonyítható. Egy 100 csúcsú páros gráf maximális élszáma Mantel tétele alapján $50 \times 50 = 2500$. A 199 él elhelyezhető úgy, hogy a gráf megőrizze páros mivoltát, például egy 100 csúcsú fához adva további éleket a különböző színosztályok között.
18
Egy összefüggő gráfról tudjuk, hogy bármely élének elhagyásával a gráf elveszíti az összefüggőségét. Milyen tulajdonságú ez a gráf?
Ez a tulajdonság azt jelenti, hogy a gráf minden éle elvágó él, más néven híd. Mivel egyetlen él elhagyása sem tarthatja egyben a gráfot, nem tartalmazhat kört. Egy körmentes és összefüggő gráf definíció szerint egy fa.
19
Mely feltételek mellett alkot egy $K_{m,n}$ teljes páros gráf fát?
A gráf csúcsainak száma $m+n$, éleinek száma $mn$. A fa feltétele, hogy éleinek száma eggyel kevesebb legyen a csúcsok számánál, azaz $mn = m+n-1$. Átrendezve kapjuk az $(m-1)(n-1) = 0$ egyenletet. Tehát vagy $m=1$, vagy $n=1$, azaz a gráfnak egy csillaggráfnak kell lennie.
20
Egy összefüggő $n$ csúcsú gráf minden csúcsának foka pontosan 2. Hány feszítőfája van ennek a gráfnak?
Ha egy összefüggő gráf minden csúcsának foka 2, akkor az a gráf pontosan egy $n$ hosszú kör ($C_n$). A körből bármelyik egyetlen élet elhagyva egy $n-1$ élből álló utat kapunk, amely egyben feszítőfa. Mivel $n$ darab él közül választhatunk elhagyandót, pontosan $n$ darab feszítőfája létezik.