- 1. feladat Ö M
Tegyük fel, hogy az egyszerű
n
pontú
G
gráfban
3
n
−
1
∕
2
-nél több él van. Bizonyítsuk be, hogy tartalmaz
Θ
-gráfot, azaz azonos pontpárt összekötő három
független utat.
- 2. feladat Ö M
(a) Ha egy egyszerű
G
gráf minden pontjának foka legalább 3, akkor
G
tartalmaz kört húrral.
(b) Ha az egyszerű
G
gráfnak
n
≥
4
pontja és
2
n
−
3
éle van, akkor tartalmaz kört húrral.
- 3. feladat Ö M
(a) Tegyük fel, hogy az egyszerű
G
gráfban minden pont foka legalább 3. Bizonyítsuk
be, hogy tartalmazza
K
4
egy felosztását.
(b) Tegyük fel, hogy
G
n
pontú,
2
n
−
2
élű egyszerű gráf. Bizonyítsuk be, hogy
G
tartalmazza
K
4
egy felosztását.
- 4*. feladat Ö M
Legyen
G
egyszerű gráf, melyben minden fokszám legalább 3,
és melyben nincsen két diszjunkt kör. Bizonyítsuk be, hogy ekkor
G
a következő gráfok egyike: (i)
K
5
, (ii) egy kerék, (iii)
K
3
,
n
−
3
a 3 elemű osztálybeli pontokat összekötő bármely
élhalmaz hozzáadásával (8. ábra).
- 5. feladat Ö M
(a) Minden egyszerű, 2-szeresen összefüggő,
n
≥
5
pontú és
2
n
−
2
élű gráf tartalmazza
K
2
,
3
egy felosztását.
(b) Minden egyszerű, 3-szorosan összefüggő,
n
≥
6
pontú és
3
n
−
5
élű gráf tartalmazza
K
3
,
3
egy felosztást.
(c) Hány él garantálja rendre
K
2
,
3
és
K
3
,
3
felosztásának létezését a fenti összefüggőségi
feltételek nélkül?
- 6. feladat Ö M
(a) Ha egy egyszerű
G
gráf összehúzható
K
4
-gyé, akkor is
K
4
egy felosztását is tartalmazza.
(b) Ez
K
4
helyett
K
5
-re nem igaz. Keressünk 4-szeresen összefüggő
ellenpéldát!
- 7. feladat Ö M
Legyen
G
m
élű és
n
pontú egyszerű gráf. Bizonyítsuk be, hogy
tartalmaz olyan összefüggő (nem feszítő)
G
1
részgráfot, melyre
G
1
szomszédai (vagyis
V
G
−
V
G
1
azon pontjai, melyek szomszédosak
G
1
valamely pontjával) olyan gráfot feszítenek,
melyben minden pont foka nagyobb
m
n
−
1
-nél.
- 8. feladat Ö M
Legyen
G
egyszerű
n
pontú gráf,
m
≥
3
és
|
E
G
|
≥
2
m
−
3
n
. Ekkor
G
összehúzható
K
m
-mé.
- 9. feladat Ö M
Legyen
F
tetszőleges
k
élű gráf, melyben nincsenek hurokélek és izolált
pontok. Bizonyítsuk be, hogy ha
G
egyszerű gráf, melyre
akkor
G
tartalmazza
F
egy felosztását.
- 10. feladat Ö M
Határozzuk meg a legkisebb 4, illetve 5 kerületű
3-reguláris gráfot.
- 11. feladat Ö M
Ha egy
r
-reguláris
G
gráf kerülete
g
, akkor
- 12. feladat Ö M
Legyen
r
≥
2
és
g
≥
2
adott. Ekkor létezik
r
-reguláris
g
kerületű gráf.
- 13. feladat Ö M
Legyen
G
a lehető legkevesebb ponton értelmezett
r
-reguláris, legalább
g
kerületű gráf. Bizonyítsuk be a következő
állításokat:
(a)
G
átmérője legfeljebb
g
.
(b)
G
kerülete
g
.
(c)
|
V
G
|
≤
r
r
−
2
r
−
1
g
.
- 14. feladat Ö M
Ha az
r
-reguláris
G
gráf (
r
≥
2
) kerülete legalább
g
, és pontszáma
2
n
≥
4
r
g
, akkor
G
beágyazható egy
r
+
1
-reguláris, legalább
g
kerületű, azonos ponthalmazon értelmezett
gráfba.
- 15. feladat Ö M
(a) Konstruáljunk
p
+
1
-reguláris,
2
p
2
+
p
+
1
pontú, 6 kerületű gráfot (
p
prím).
(b)* Konstruáljunk
p
+
1
-reguláris,
2
p
3
+
p
2
+
p
+
1
pontú, 8 kerületű gráfot (vö. 10.11).
- 16. feladat Ö M
(a) Legyen
G
olyan
n
pontú gráf, melyben
3
≤
d
G
x
≤
d
minden
x
pontra. Ekkor
G
összes körének lefogásához legalább
n
+
2
d
+
1
pontra van szükség.
(b) Ha
G
kerülete
g
és legkisebb fokszáma legalább 3, akkor
G
összes körének lefogásához legalább
3
8
2
g
∕
2
pontra van szükség.
- 17*. feladat Ö M
Legyen
G
olyan gráf, melyben minden pont foka legalább 3,
és melynek kerülete
g
≥
3
. Mutassuk meg, hogy ekkor
G
tartalmaz
3
8
g
2
g
∕
2
diszjunkt kört.
- 18. feladat Ö M
Minden
G
gráfra jelölje
ν
a
G
-beli diszjunkt körök maximális számát,
τ
pedig az összes
G
-beli kör lefogásához szükséges pontok minimális
számát. Bizonyítsuk be, hogy
(a) ha
ν
=
1
, akkor
τ
≤
3
,
(b)
τ
≥
ν
≥
τ
4
log
τ
,
(c)
τ
végtelen sok értékére létezik olyan
G
gráf, melyre
- 19. feladat Ö M
Legyen
G
2-szeresen összefüggő gráf,
x
,
y
∈
V
G
, és tegyük fel, hogy minden
x
-től és
y
-tól különböző pont foka legalább
k
. Bizonyítsuk be, hogy
x
és
y
összeköthető legalább
k
hosszúságú úttal.
- 20*. feladat Ö M
Legyen
G
olyan egyszerű gráf, melyben minden
X
⊂
V
G
,
|
X
|
≤
k
-ra
Bizonyítsuk be, hogy
G
tartalmaz
3
k
−
2
hosszú utat.
- 21. feladat Ö M
Legyenek az
n
pontú, egyszerű
G
gráf pontjainak fokai
d
1
≤
d
2
≤
…
≤
d
n
. Bizonyítsuk be, hogy
G
-ben van Hamilton kör, ha az alábbi feltételek
közül bármelyiknek is eleget tesz:
(a) (Dirac feltétel)
d
1
≥
n
∕
2
,
(b) (Pósa feltétel)
d
k
≥
k
+
1
,
k
<
n
2
-re,
(c) (Bondy feltétel)
d
l
≤
l
,
d
k
≤
k
-ból következik, hogy
d
l
+
d
k
≥
n
(
k
≠
l
),
(d) (Chvátal feltétel)
d
k
≤
k
<
n
2
-ből következik, hogy
d
n
−
k
≥
n
−
k
.
- 22. feladat Ö M
Ha
G
olyan
n
pontú, egyszerű gráf, melyben minden fokszám
legalább
n
+
q
2
, akkor bármely diszjunkt utakat alkotó
q
élből álló
F
halmazt tartalmaz egy Hamilton kör.
- 23*. feladat Ö M
Legyen
G
n
-reguláris egyszerű
2
n
+
1
pontú gráf. Bizonyítsuk be, hogy
G
-ben van Hamiltor-kör.
- 24. feladat Ö M
Az egyszerű
n
≥
2
pontú
G
gráfban minden pont foka nagyobb
n
∕
2
-nél. Mutassuk meg, hogy
G
bármely két pontja összeköthető Hamilton
úttal.
- 25. feladat Ö M
Legyen
G
egyszerű
n
pontú irányított gráf, melyben minden pont befoka
is és kifoka is legalább
n
∕
2
. Bizonyítsuk be, hogy
G
tartalmaz irányított Hamilton kört (vö.
10.21a).
- 26. feladat Ö M
Legyen
G
olyan egyszerű
k
-szorosan összefüggő gráf, mely nem tartalmaz
k
+
1
méretű független ponthalmazt (
k
≥
2
). Mutassuk meg, hogy
G
-ben van Hamilton kör.
- 27. feladat Ö M
Legyen
G
olyan egyszerű
n
pontú gráf, melyben minden pont foka legalább
k
. Ekkor
(a)
G
tartalmaz legalább
k
+
1
hosszúságú kört,
(b)* ha
G
2-szeresen összefüggő, akkor tartalmaz vagy egy legalább
2
k
hosszúságú kört vagy egy Hamilton kört.
- 28. feladat Ö M
Legyen
G
egyszerű
n
pontú gráf, melyben
k
n
−
1
2
-nél több él van (
2
≤
k
<
n
). Ekkor
G
tartalmaz legalább
k
+
1
hosszúságú kört.
- 29*. feladat Ö M
Legyen
G
egyszerű 2-szeresen összefüggő gráf és legyen
l
a
G
-beli körök maximális hossza. Ekkor
G
nem tartalmaz
l
2
4
+
1
hosszúságú utat.
- 30. feladat Ö M
Az egyszerű
n
pontú
G
gráf nem tartalmaz háromszöget. Mutassuk meg, hogy
- 31. feladat Ö M
Ha
G
egyszerű háromszögmentes gráf, akkor
Vezessük le ebből az előző eredményt.
- 32. feladat Ö M
(a) Ha
G
egyszerű
n
pontú
k
-reguláris gráf, akkor
G
és
G
¯
háromszögeinek együttes száma
(b) Bármely egyszerű
n
pontú
G
gráf és annak
G
¯
komplementere együtt legalább
háromszöget tartalmaz.
- 33. feladat Ö M
Egy
n
pontú és
m
élű gráf háromszögeinek száma legalább
- 34. feladat (Turán tétele) Ö M
Tegyük fel, hogy az egyszerű
G
gráfnak
m
k
pontja és
k
2
m
2
-nél több éle van. Bizonyítsuk be, hogy
G
tartalmaz teljes
k
+
1
-szöget. Általánosítsuk a tételt az
n
=
m
k
+
r
,
1
≤
r
≤
k
−
1
esetre.
- 35. feladat Ö M
Tegyük fel, hogy
G
egyszerű gráf, mely nem tartalmaz teljes
k
+
1
-szöget. Mutassuk meg, hogy létezik
V
G
-n olyan egyszerű
k
-kromatikus
H
gráf, melyre
Vezessük le ebből Turán tételét.
- 36. feladat Ö M
(a) Minden egyszerű
n
pontú gráf, melynek legalább
n
4
1
+
4
n
−
3
éle van, tartalmaz négyszöget (4 hosszú
kört).
(b) Ha
n
=
p
2
+
p
+
1
(
p
prím), akkor létezik olyan 4 hosszú kört nem
tartalmazó egyszerű
n
pontú gráf, melynek
1
2
p
p
+
1
2
∼
1
2
n
3
∕
2
éle van.
- 37. feladat Ö M
Tegyük fel, hogy az egyszerű
n
pontú és
m
élű
G
gráf nem tartalmaz
K
r
,
r
-t. Bizonyítsuk be, hogy
ahol
C
csak
r
-től függ.
- 38*. feladat (Erdős–Stone tétel) Ö M
(a) Legyen
ɛ
>
0
és
k
,
t
≥
1
adott. Bizonyítsuk be, hogy ha
n
elég nagy, akkor minden olyan
n
pontú gráf, melyben minden pont foka legalább
1
−
1
∕
k
+
ɛ
n
, tartalmaz
k
+
1
diszjunkt
t
méretű halmazt, melyekre bármely két különböző
halmazba tartozó pont szomszédos.
(b) Legyen
G
egyszerű,
n
pontú és
1
−
1
∕
k
+
ɛ
n
2
2
élű gráf. Ekkor ha
n
elég nagy,
G
tartalmaz
k
+
1
diszjunkt
t
méretű halmazt, melyekre bármely két különböző
halmazba tartozó pont szomszédos.
(c) Minden
G
0
gráfra jelöljük
M
n
,
G
0
-lal az olyan egyszerű
n
pontú gráf éleinek maximális számát, mely nem
tartalmaz
G
0
-lal izomorf részgráfot. Bizonyítsuk be, hogy
- 39*. feladat Ö M
Legyen
G
0
olyan
k
+
1
-kromatikus egyszerű gráf, hogy valamely
e
élre
G
0
−
e
k
-színezhető. Bizonyítsuk be, hogy a 10.34
megoldásában szereplő
H
n
,
k
gráf nem tartalmazza
G
0
-t, de ha
n
elég nagy, akkor bármely más gráf ugyanezzel az
élszámmal már tartalmazza
G
0
-t részgráfként. Tehát
H
n
,
k
az egyetlen extrém gráf.
- 40*. feladat Ö M
Legyen
G
egyszerű
n
pontú gráf és jelölje
N
k
a
G
-beli teljes
k
-gráfok számát. Bizonyítsuk be, hogy
(a)
N
k
+
1
N
k
≥
1
k
2
−
1
k
2
N
k
N
k
−
1
−
n
.
(b) Ha
E
G
=
1
−
1
ϑ
n
2
2
, akkor
N
k
≥
ϑ
k
n
ϑ
k
k
≤
ϑ
+
1
,
ϑ
valós
.
- 41. feladat Ö M
(a) Egy
n
pontú
T
turnament legfeljebb
1
4
n
+
1
3
darab 3 hosszúságú irányított kört
tartalmaz.
(b) Egy erősen összefüggő,
n
pontú
T
turnament legalább
n
−
2
darab 3 hosszúságú irányított kört
tartalmaz.
- 42. feladat Ö M
Egy erősen összefüggő,
n
pontú
T
turnament legalább
n
−
1
2
irányított kört tartalmaz.
- 43. feladat Ö M
Egy
n
pontú turnament legfeljebb egy és legalább
n
!
∕
2
n
∕
2
Hamilton utat tartalmaz.
- 44. feladat Ö M
(a) Minden
n
pontú
T
turnament tartalmaz egy
⌊
log
2
n
⌋
+
1
pontú tranzitív részturnamentet.
(b) A
k
elemű (
1
≤
k
≤
log
2
n
) tranzitív rész-turnamentek száma legalább
(c) Ha
T
erősen összefüggő, akkor a
k
elemű (
k
≥
3
) tranzitív rész-turnamentek száma legfeljebb