- 1. feladat F M
Tekintsünk egy maximális (nem bővíthető)
független halmazt.
- 2. feladat F M
Legyen
S
1
a
G
egy maximális független halmaza és
legyen
S
i
+
1
maximális független halmaz
G
−
S
1
−
…
−
S
i
-ben. Mutassuk meg, hogy van olyan
párosítás
G
-ben, mely
S
i
+
1
-t
S
i
egy részhalmazával párosítja.
- 3. feladat F M
Keressünk olyan kört vagy élt, mely tartalmaz egy
x
pontot és
x
minden szomszédját.
- 4. feladat F M
Ha
(
x
,
y
)
∈
E
(
G
)
, ahol
x
,
y
∈
S
, akkor tekintsük
G
−
x
-et.
- 5. feladat F M
(a) Vegyünk egy tetszőleges maximális (nem
bővíthető) független halmazt.
(b) Alkalmazzunk indukciót egy 0 befokú pont és
szomszédainak elhagyásával.
(c) Használjuk 5.3-at.
- 6. feladat F M
Vegyük a legnagyobb kifokú pontot.
- 7. feladat F M
Hagyjunk el egy pontot és az összes olyan pontot,
mely ebből egy élen elérhető, és alkalmazzunk
indukciót.
- 8. feladat F M
(a) Vegyük észre, hogy az, hogy a soron következő
játékos nyerhet-e, csak az ellenfél legutóbbi lépésén
múlik; nevezzük ezt az utolsó lépést „nyerő lépésnek”
(az ellenfél számára), ha a soron következő játékos nem
tud nyerni. Mik a nyerő lépések halmazának jellemző
tulajdonságai?
(b) Az
x
0
pontot csak akkor foglalja el bárki
is, ha
A
ezzel kezd.
(c) Vegyük észre, hogy ha egyszer elhagytak egy
komponenst, ott nem tesznek több lépést.
- 9. feladat F M
Ha
G
-ben nincs 1-faktor,
A
-nak egy maximális párosítást célszerű
választani, és egy ebbe nem tartozó ponttal
kezdeni.
- 10. feladat F M
Alkalmazzunk indukciót
k
-ra.
- 11. feladat F M
Érveljünk az előző feladathoz hasonlóan.
- 12. feladat F M
Hagyjunk el egy
x
-re illeszkedő élt.
- 13. feladat F M
Elég arra az esetre bizonyítani az állítást,
amikor egyetlen
x
pontot helyettesítünk két szomszédos
x
1
,
x
2
ponttal, melyek ugyanazon „régi”
pontokhoz csatlakoznak, mint
x
.
- 14. feladat F M
Elég az adott
G
0
gráfot egy
G
gráfba beágyazni úgy, hogy
α
(
G
−
e
)
>
α
(
G
)
fennálljon
G
0
éleire.
- 15. feladat F M
(a) Az
r
=
2
esetben a páratlan körök megfelelnek.
Ha
r
>
2
, növeljük a fokszámot úgy, hogy
pontokat teljes gráffal helyettesítünk.
(b) A tetraéder és az ikozaéder.
- 16. feladat F M
Egy
α
-kritikus páros gráf független élekből
áll. Feltéve, hogy valamely
x
∈
V
(
G
)
két
y
1
,
y
2
ponttal van összekötve, tekintsük a
G
−
(
x
,
y
i
)
egy maximális független
S
i
halmazát és az
S
1
△
S
2
∪
{
x
}
által feszített részgráfot (vö. 7.2
megoldásával).
- 17. feladat F M
Kövessük az előző megoldást.
- 18. feladat F M
Tegyük fel, hogy
S
egy teljes gráfot feszítő minimális
vágás-halmaz és
x
∈
S
, ekkor tekintsünk két élt, melyek
x
-et
G
−
S
különböző komponenséhez kötik.
- 19. feladat F M
(a) Mutassuk meg, hogy
α
(
G
)
=
α
(
G
1
)
+
α
(
G
2
)
.
(b) Tegyük fel, hogy
G
=
G
1
∪
G
2
úgy, hogy
V
(
G
1
)
∩
V
(
G
2
)
=
{
x
,
y
}
, és
|
V
(
G
i
)
|
≥
3
. Határozzuk meg minden
X
⊆
{
x
,
y
}
-ra és
i
=
1
,
2
-re a
G
i
olyan független halmazának maximális
méretét, mely
{
x
,
y
}
-t
X
-ben metszi; írjuk fel evégett az ezen
számokra vonatkozó lineáris egyenlőtlenségeket.
- 20. feladat F M
Alkalmazzuk 8.10-et a maximális független
halmazok halmazával.
- 21. feladat F M
Alkalmazzuk 8.11-et.
- 22. feladat F M
Legyen
{
T
1
,
…
,
T
k
}
az
x
-et tartalmazó maximális független
halmazok halmaza; alkalmazzuk ismét 8.11-et.
- 23. feladat F M
(a) Használjuk az előző eredményt. (b) Használjuk
(a)-t.
- 24. feladat F M
Ezek csak a teljes gráfok és páratlan körök;
mutassuk meg és használjuk fel a tényt, hogy ha
T
,
S
maximális független halmazok, melyekre
T
∩
S
≠
∅
, akkor
Γ
(
T
∪
S
)
=
V
(
G
)
−
T
−
S
.
- 25. feladat F M
Használjuk 8.19-et és az előző feladatot.
- 26. feladat F M
Tekintsünk egy
α
-kritikus feszítő részgráfot.
- 27. feladat F M
Tekintsük ismét a
G
egy
α
-kritikus feszítő részgráfját.