- 1. feladat F Ö
Feltehetjük, hogy
G
2-szeresen összefüggő. Hiszen ha
G
=
G
1
∪
G
2
és
V
(
G
1
)
∩
V
(
G
2
)
≤
1
,
V
(
G
i
)
≥
2
, akkor
G
1
és
G
2
egyike eleget tesz a
egyenlőtlenségnek, és alkalmazhatunk
indukciót
n
-re.
Tehát tegyük fel, hogy
G
2-szeresen összefüggő. Nyilvánvaló,
hogy nem egyetlen kör, így 6.33 szerint
G
=
P
0
∪
P
1
∪
…
∪
P
k
(
k
≥
1
), ahol
P
0
egy kör és
P
i
+
1
egy
(
P
0
∪
…
∪
P
i
,
P
0
∪
…
∪
P
i
)
út
i
=
0
,
…
,
k
−
1
-re. Ekkor
P
0
∪
P
1
egy
Θ
-gráf.
Az eredmény élességét mutatja minden olyan gráf,
melynek tagjai háromszögek.
- 2. feladat F Ö
(a) Legyen
P
=
(
x
0
,
x
1
,
…
,
x
p
)
a
G
-beli leghosszabb út.
X
0
két ponttal szomszédos
x
1
-en kívül; mivel
P
maximális, ennek a két pontnak rajta
kell lenni
P
-n; legyen
x
0
mondjuk
x
i
-vel és
x
j
-vel szomszédos,
2
≤
i
<
j
≤
p
. Ekkor
(
x
0
,
…
,
x
j
)
egy olyan kör
G
-ben, melynek
(
x
0
,
x
i
)
húrja. [Czipszer J.]
(b) Indukciót alkalmazunk
n
-ra. Az állítás
n
=
4
-re nyilvánvaló. Ha
G
-ben minden pont foka legalább 3,
akkor (a) miatt tartalmaz kört húrral.
Tehát feltehetjük, hogy
G
-nek van legfeljebb 2 fokú
x
pontja. Ekkor
G
−
x
tartalmaz legalább
2
n
−
3
−
2
=
2
(
n
−
1
)
−
3
élt, és így indukciós feltevés szerint
G
−
x
tartalmaz kört húral. De ekkor ez
G
-re is igaz.
K
2
,
n
−
2
mutatja, hogy a (b)-beli eredmény
éles. [Pósa L.]
- 3. feladat F Ö
(a)
V
(
G
)
szerinti indukcióval bizonyítjuk az
ötlettár állítását.
I. Először tegyük fel, hogy
G
-ben van egy legfeljebb 2 fokú
x
pont. Ha
x
foka 1, akkor
G
−
x
-ben legfeljebb egy legfeljebb 2 fokú
pont van, így az indukcióval készen vagyunk. Ha
x
foka 2, azaz két ponttal,
y
-nal és
z
-vel szomszédos és
(
y
,
z
)
∉
E
(
G
)
, akkor hagyjuk el
x
-et és kössük össze
y
-t
z
-vel. A kapott gráfban minden fokszám
legalább 3, így tartalmazza
K
4
egy felosztását is. Ha
y
és
z
szomszédosak, akkor feltehetjük, hogy
d
G
(
y
)
=
d
G
(
z
)
=
3
(egyébként
G
−
x
eleget tesz a feltételnek). Ha
y
és
z
harmadik szomszédja ugyanaz a
w
pont, akkor
G
−
x
−
y
−
z
−
w
eleget tesz a feltételnek; ha
y
szomszédos
u
-val,
z
pedig
v
-vel, (
x
,
y
,
z
,
u
és
v
különbözőek) akkor
x
-et,
y
-t és
z
-t egyetlen
x
′
pontba összehúzva olyan
G
′
gráfot kapunk, melyben csak
x
′
foka legfeljebb 2. Így
G
′
tartalmazza
K
4
felosztását. Mivel
G
′
(
x
′
,
u
)
élét felosztva
G
egy részgráfját kapjuk,
G
szintén tartalmazza
K
4
egy felosztását (lásd 72.
ábra).
II. Tegyük fel, hogy
G
minden pontjának foka legalább 3.
Feltehetjük, hogy
G
-ben van egy harmadfokú
x
pont, különben elhagyhatnánk éleket.
Legyenek
u
,
v
és
w
az
x
-szel szomszédos pontok. Ha
u
,
v
és
w
páronként szomszédosak, akkor
x
,
u
,
v
és
w
K
4
-et feszítenek. Tehát feltehetjük,
hogy
(
u
,
v
)
∉
E
(
G
)
. Hagyjuk el
x
-et és kössük össze
u
-t
v
-vel. A kapott
G
′
gráfban minden pont foka legalább 3
esetleg
w
kivételével, mely lehet másodfokú. Így
indukcióval
G
′
tartalmazza
K
4
felosztását. Mivel az
(
u
,
v
)
élet
x
-szel felosztva
G
egy részgráfját kapjuk,
G
szintén tartalmazza
K
4
felosztását.
(b) Ha
G
minden pontjának foka legalább 3,
akkor (a) szerint készen vagyunk. Ha van egy másodfokú
pont, akkor azt elhagyva indukciót alkalmazunk.
A 73. ábrán látható gráfban pontosan két
másodfokú pont és
2
n
−
3
él van, és nem tartalmazza
K
4
felosztását (bizonyítsuk!). Tehát (a)
is és (b) is éles. [G. Dirac, Math. Nachr. 22 (1960)
61–85]
- 4. feladat F Ö
Először az ötletet követve azt bizonyítjuk, hogy
G
nem tartalmazza
K
4
egy
H
felosztását és egy attól diszjunk
(
u
,
v
)
élt. Tegyük fel, hogy tartalmaz ilyet.
Nézzük
G
−
V
(
H
)
-nek az
(
u
,
v
)
-t tartalmazó
G
1
komponensét. Ez triviálisan egy fa.
Legyen
x
és
y
a
G
1
két végpontja. Ekkor
x
-nek (illetve
y
-nak) van két szomszédja
H
-ban,
p
1
és
p
2
(illetve
q
1
és
q
2
).
H
fő pontjai „felosztott csillagainak”
sem középpontja, sem a „sugarainak” belső pontja nem
lehet
p
1
,
p
2
,
q
1
és
q
2
közül kettő, hiszen az ilyen helyzet
két diszjunkt kört eredményezne (74.a ábra). De ekkor
könnyen ellenőrizhető, hogy
p
1
,
p
2
,
q
1
és
q
2
kell, hogy legyenek
H
fő pontjai, ami megint két diszjunk
kört eredményez a 74.b ábra szerint.
Ezek után meg kell különböztetnünk 5
esetet:
1. eset. Tegyük fel, hogy
G
-ben van
K
4
-nek egy
H
felosztása és egy
H
-n kívüli legalább 4 fokú
v
pont. A fentihez hasonló érvelés
mutatja, hogy
v
foka pontosan 4, és szomszédos
H
négy fő pontjával, ezek
x
1
,
x
2
,
x
3
és
x
4
.
x
i
és
v
szerepét felcserélve felhasználhatjuk
az ötlettár állítását és láthatjuk, hogy
x
i
-nek szomszédosnak kell lenni
x
j
-vel (
j
≠
i
) és
v
-vel, de semmilyen más ponttal sem.
Emiatt
G
=
K
5
.
2. eset. Tegyük fel, hogy
G
tartalmazza
K
4
egy
H
felosztását és egy harmadfokú
v
pontot, mely nem
H
-beli, de szomszédos
H
három fő pontjával. Legyenek ezek
x
1
,
x
2
és
x
3
. Felcserélve
v
és a negyedik fő pont,
x
4
szerepét, azt kapjuk, hogy
Γ
(
x
4
)
=
{
x
1
,
x
2
,
x
3
}
. Megmutatjuk, hogy
G
minden
(
r
,
s
)
éle tartalmazza
x
1
,
x
2
és
x
3
egyikét. Tegyük fel, hogy ez nem így
van. Ekkor
r
,
s
≠
x
1
,
x
2
,
x
3
,
x
4
,
v
. De
x
1
,
x
2
,
x
3
,
x
4
és
v
a felosztott élek,
(
x
1
,
x
2
)
,
(
x
2
,
x
3
)
és
(
x
1
,
x
3
)
bármelyikével együtt
K
4
egy felosztását alkotja. Így
(
r
,
s
)
-nek ezen felosztott élek mindegyikét
belső pontban kell érintenie, ami lehetetlen. Tehát
x
1
,
x
2
és
x
3
valóban lefog minden pontot. De ez
természetesen azt jelenti, hogy egy (iii)-nak megfelelő
gráfunk van.
3. eset. Van
g
-ben
K
4
-nek egy
H
felosztása és egy azon kívüli
harmadfokú
v
pont, mely
H
-nak legfeljebb két fő pontjával van
összekötve. az ötlettár állítása szerint
v
szomszédainak
H
-ban kell lenni, és könnyen látható,
hogy közülük legalább kettőnek, mondjuk
x
1
-nek és
x
2
fő pontnak kell lenni. Mivel a
harmadik szomszédja nem fő pont, annak a felosztott
(
x
3
,
x
4
)
él egy
p
belső pontjának kell lenni.
x
3
és
v
szerepét felcserélve azt kapjuk, hogy
Γ
(
x
3
)
=
{
x
1
,
x
2
,
p
}
, és hasonlóan
Γ
(
x
4
)
=
{
x
1
,
x
2
,
p
}
. Azt állítjuk, hogy
x
1
,
x
2
és
p
minden élt lefog; ekkor az előbbiekhez
hasonló következtetésre jutunk. Mivel
x
1
,
x
2
,
x
3
,
x
4
és
p
tartalmazza
K
4
egy felosztását, minden élnek
érintenie kell ezen pontok egyikét. De azok, melyek az
x
3
,
x
4
vagy
v
pontot érintik, illeszkednek még az
x
1
,
x
2
vagy
p
ponthoz is. Ezzel ezt az esetet is
elintéztük.
4. eset. Így feltehetjük, hogy
K
4
minden felosztása feszítő részgráf.
10.3.a szerint
G
tartalmazza
K
4
egy
H
felosztását. Legyenek
x
1
,
x
2
,
x
3
és
x
4
ennek fő pontjai. Tegyük fel, hogy ez
a felosztott
K
4
választható úgy, hogy
x
1
foka legalább 4. Legyen
(
x
1
,
u
)
egy
x
1
-gyel szomszédos nem
H
-beli él. Mivel
H
egy feszítő részgráf,
u
a
H
egy pontja;
u
-nak triviálisan a
H
−
x
1
C
körén kell lenni. A felosztott
(
x
1
,
x
i
)
(
i
=
2
, 3, 4) élt
(
x
1
,
u
)
-val helyettesítve feszítő felosztott
K
4
-eket kell kapnunk. Így
x
1
szomszédos
x
2
-vel,
x
3
-mal és
x
4
-gyel.
C
bármely pontja triviálisan csak
x
1
-gyel lehet szomszédos (kivéve a
C
-n lévő szomszédait). Tehát
G
egy kerék.
5. eset. Már csak az az eset van hátra, amikor
G
-ben minden felosztott
K
4
egy feszítő részgráf, és fő pontjainak
G
-beli foka 3. Ha
G
=
K
4
, akkor egy kerék. Így tegyük fel,
hogy
H
-nak van egy
e
húrja, melynek ekkor
H
két felosztott élének belső pontját
kell összekötni. Nyilvánvaló, hogy ezen felosztott élek
diszjunktak, pl.
(
x
1
,
x
2
)
és
(
x
3
,
x
4
)
.
G
nem tartalmaz további pontokat, hiszen
egy ilyen pontot elhagyva
H
+
e
megmaradó része még mindig tartalmazná
K
4
egy felosztását, ami ellentmond a
feltételnek. Így
G
-nek hat pontja van, ez triviális
eset.
Megjegyzés: Hasonló érveléssel minden olyan (nem
feltétlenül egyszerű) gráfot meghatározhatnánk, mely
nem tartalmaz két diszjunkt kört. Ha adva van egy ilyen
gráf, elhagyhatunk elsőfokú, és „kisimíthatunk”
másodfokú pontokat, így elegendő a legalább harmadfokú
ilyen gráfokat meghatároznunk. Az eredmény a következő:
a feladatban leírt három fajta gráf azzal a
módosítással, hogy a kerék küllői és
K
3
,
n
−
3
3 elemű osztályának élei lehetnek
többszörösek; és van egy új osztály: vegyünk egy
F
erdőt és egy
x
pontot, melyhez illeszkedhetnek
hurokélek, és tetszőlegesen kössük
x
-et
F
-hez. [G. A. Dirac,
Canad. Math. Bull. 8 (1965) 459–463;
Lovász L., Mat. Lapok 16 (1965) 289–299]
- 5. feladat F Ö
(a) 10.3b szerint
G
tartalmazza
K
4
egy felosztását. Ha ez a felosztás
valódi, azaz a felosztott élek legalább egyikének van
belső pontja, akkor könnyen megtaláljuk
K
2
,
3
egy felosztását. Így feltehetjük, hogy
G
négy páronként szomszédos élt
tartalmaz, ezek
x
,
y
,
z
és
u
. Mivel
n
≥
5
, van még legalább egy
v
pont. Tekintve, hogy
G
2-szeresen összefüggő, van két
független út, melyek
v
-t
x
,
y
,
z
és
u
közül különbözőekkel kötik össze. Így
x
,
y
,
z
,
u
és
v
a
K
2
,
3
egy felosztásának fő pontjai (75.
ábra).
(b) Mivel
E
(
G
)
≥
3
n
−
5
, 4.26-ből az következik, hogy
G
nem síkbarajzolható, és így Kuratowski
tétele (5.37d) szerint
G
tartalmazza
K
3
,
3
vagy
K
5
egy felosztását. Az első esetben
készen vagyunk, így tegyük fel, hogy
G
tartalmazza
K
5
egy felosztását az
x
1
,
…
,
x
5
fő pontokkal. Ugyanúgy, mint az (a)
részben, különbséget kell tennünk a két eset között
aszerint, hogy ez a felosztás valódi-e,
1
∘
Tegyük fel, hogy a felosztott
(
x
1
,
x
2
)
él, legyen ez mondjuk
Q
, tartalmaz belső pontokat.
G
−
{
x
1
,
x
2
}
összefüggő, ezért van egy
P
út, mely
Q
egy belső
y
pontját egy
Q
-n kívüli
z
ponttal köti össze.
z
-nek három lényegesen különböző
helyzete lehet, de minden esetben könnyen megtaláljuk
K
3
,
3
egy felosztását (lásd 76.
ábra).
2
∘
Tegyük fel, hogy
x
1
,
…
,
x
5
kölcsönösen szomszédosak. Mivel
n
≥
6
, kell lennie egy további
v
pontnak. Tudjuk, hogy
G
3-szorosan összefüggő, ezért van három
független
v
-t (mondjuk)
x
1
-gyel,
x
2
-vel és
x
3
-mal összekötő út. Ekkor ismét
nyilvánvalóan megtaláltuk
K
3
,
3
egy felosztását. (77. ábra).
(c) Azt állítjuk, hogy ha egy gráfban legalább
2
n
−
2
él van, és nem tartalmazza
K
3
,
2
egy felosztását, akkor összefüggő, és
tagjai
K
4
-ek. Indukciót alkalmazunk
n
-re.
Először tegyük fel, hogy egy
2
n
−
2
élű
G
gráf nem összefüggő, azaz
G
=
G
1
∪
G
2
,
G
∩
G
2
=
∅
. Legyen
V
(
G
1
)
=
n
i
>
0
(
i
=
1
, 2). Ekkor
ami miatt pl.
Tehát indukcióval azt kapjuk, hogy
G
1
összefüggő és minden tagja
K
4
. De ekkor
E
(
G
1
)
=
2
n
1
−
2
, ami ellentmondás. Így
G
összefüggő.
Ha
G
2-szeresen összefüggő, akkor az
állítás (a)-ból következik. Így tegyük fel, hogy van
egy elvágópontja, ez
x
. Legyen
G
=
G
1
∪
G
2
,
V
(
G
1
∩
G
2
)
=
{
x
}
,
V
(
G
i
)
=
n
i
<
n
. Ekkor
Mint az előbb, itt is ellentmondást kapunk,
ha
bármely
i
-re. Ebből tehát az következik, hogy
és az indukciós feltevés miatt
G
1
és
G
2
összefüggő gráfok, melyeknek tagjai
K
4
-ek. Tehát
G
is ilyen.
Hasonló érveléssel adódik, hogy ha
G
n
pontú és
3
n
−
5
élű gráf, mely nem tartalmazza
K
3
,
3
egy felosztását, akkor
G
2-szeresen összefüggő, és 5 pontú
teljes gráfokból építhető fel a következő rekurzív
szabály szerint: Veszünk egy (már megkonstruált)
G
gráfot és egy 5 pontú teljes
K
5
gráfot, és azonosítjuk
G
egy élét
K
5
egy élével (lásd 79.a ábra).
Tehát a (c)-re adott válasz a következő: Minden
n
pontú és
gráf tartalmazza
K
2
,
3
egy felosztását; minden
n
pontú és
gráf tartalmazza
K
3
,
3
egy felosztását. Ezek a korlátok a
lehető legjobbak, mint azt a 78. és
79. ábrán látható
gráfok mutatják. [Pósa L.]
- 6. feladat F Ö
Megmutatjuk, hogy (a') ha
G
0
minden pontjának foka legfeljebb 3,
akkor bármely
G
0
-ra összehúzható gráf tartalmazza
G
0
egy felosztását; (b') ha
G
0
-nak van legalább 4 fokú pontja, akkor
ez már nem igaz.
(a')
Elég megmutatni, hogy ha
G
∕
e
(
e
=
(
u
,
v
)
∈
E
(
G
)
) tartalmazza
G
0
egy
H
felosztását, akkor
G
is. Ha
G
∕
e
azon
x
pontja, amely
e
képe, nem fő pontja
H
-nak, akkor ez nyilvánvaló; tegyük
fel, hogy
x
fő pont. A feltevés szerint
G
-ben legfeljebb 3
x
-ből kiinduló felosztott él van. Ha
u
-t és
v
-t ismét széthúzzuk, ezek közül
némelyik
u
-ból indul, némelyik
v
-ből. Feltehetjük, hogy legfeljebb egy
indul
v
-ből; ekkor
e
-t hozzávéve ehhez a felosztott élhez
és
u
-t fő pontként tekintve
G
0
egy felosztását találjuk
G
-ben.
(b') Megmutatjuk, hogy van egy
G
0
-ba összehúzható
G
0
gráf, melyben minden pont foka
legfeljebb 3. Legyen
x
a
G
0
egy legalább 4 fokú pontja. Osszuk fel
x
-et
d
elsőfokú ponttá, ezek
x
1
,
…
,
x
d
, és kössük össze ezeket egy körrel.
Tegyünk így minden legalább 4 fokú
x
ponttal; az így kapott gráfot jelölje
G
1
. Ekkor
G
1
minden pontjának foka legfeljebb 3, és
összehúzható
G
0
-ba. Ha
G
0
-ban van legalább 4 fokú pont, akkor
nyilvánvaló, hogy
G
1
nem tartalmazza
G
0
egy felosztását.
Egy 4-szeresen összefüggő ellenpélda
K
5
esetében
K
4
,
4
.
- 7. feladat F Ö
Legyen
a
∈
V
(
G
)
. Ismételten húzzunk össze éleket és
töröljük el az így adódó multiplicitásokat úgy,
hogy
(
∗
) minden összehúzott él illeszkedjen
a
képére,
(
∗
∗
)
E
(
G
′
)
V
(
G
′
)
≥
m
n
álljon fenn a kapott gráfokra.
Tegyük fel, hogy a
G
0
gráfnál akadunk el. Legyen
a
0
az
a
képe
G
0
-ban. A fenti (
∗
)-ból következik, hogy
G
-nek az a
G
1
részgráfja, melyet
a
0
-ra összehúztunk, összefüggő, és
G
−
V
(
G
1
)
=
G
0
−
a
0
.
Legyen
x
tetszőleges
a
0
-lal szomszédos pont (azaz
V
(
G
1
)
-gyel szomszédos
G
-ben). Legyen
ϑ
az
a
0
-lal és
x
-szel szomszédos pontok száma
G
0
-ban (ez
x
foka
G
-nek a
G
1
szomszédai által feszített
részgráfjában). Próbáljuk meg összehúzni
(
a
0
,
x
)
-et és hagyjunk el egy élt az így
előálló
ϑ
párhuzamos pár mindegyikéből. Ekkor (
∗
∗
) már nem állhat fenn a kapott
G
0
′
gráfra. Mivel
Következik, hogy
vagy ekvivalens alakban
Mivel
ezért
ami bizonyítja az állítást. [W.
Mader]
- 8. feladat F Ö
Indukciót alkalmazunk
m
-re.
m
=
3
-ra az állítás nyilvánvaló. Legyen
m
≥
4
. Feltehetjük, hogy
G
összefüggő.
Az előző feladat szerint
G
tartalmaz egy összefüggő
G
1
részgráfot, melynek szomszédai által
feszített
G
2
részgráfban minden pont foka nagyobb,
mint
E
(
G
)
n
−
1
≥
2
m
−
3
−
1
, így legalább
2
m
−
3
. Tehát
és így az indukciós feltevés miatt
G
2
összehúzható
K
m
−
1
-be. Ugyanezt az összehúzást
G
-re végrehajtva, majd
G
1
-et is összehúzva olyan gráfot kapunk,
mely tartalmaz
K
m
-et. [uo.]
- 9. feladat F Ö
Indukció
k
-ra:
k
=
1
-re az állítás triviális.
Megint legyen
G
1
olyan összefüggő részgráf, mint
10.7-ben, azaz legyen a
G
1
szomszédai által feszített
G
2
részgráfban minden pont foka legalább
2
k
. Ekkor
tehát
G
2
tartalmazza
F
−
e
egy
H
felosztását minden
e
∈
E
(
F
)
-re. Legyenek
x
1
és
x
4
H
-ban az
e
végpontjainak megfelelő fő pontok.
Mivel
x
i
∈
V
(
G
2
)
, ezért
x
i
szomszédos valamely
y
i
∈
V
(
G
1
)
ponttal (
i
=
1
, 2). Tekintve, hogy
G
1
összefüggő, tudjuk, hogy tartalmaz egy
P
(
y
1
,
y
2
)
utat. Ekkor
az
F
gráf egy felosztása
G
-ben. [ibid.]
- 10. feladat F Ö
I. Legyen
x
1
a 3-reguláris, 4 kerületű
G
gráf egy pontja és legyenek
x
2
,
x
3
és
x
4
a szomszédai. Ekkor
x
2
,
X
3
és
x
4
függetlenek kell, hogy legyenek, mert
G
nem tartalmaz háromszöget. Legyen
x
5
és
x
6
az
x
2
két további szomszédja. Így
V
(
G
)
≥
6
; egyenlőség csak akkor áll, ha
x
3
és
x
4
szintén
x
5
-tel és
x
6
-tal szomszédosak, azaz
G
=
K
3
,
3
.
II. Legyen
(
x
1
,
…
,
x
p
)
a legkisebb kör
G
-ben,
p
≥
5
. Legyen
y
i
az
x
i
harmadik szomszédja. A vizsgált kör
minimalitása miatt
y
i
nincsen rajta a körön és
y
i
≠
y
j
i
≠
j
esetén. Így
V
(
G
)
≥
2
p
≥
10
. Ha egyenlőség áll fenn, akkor
p
=
5
.
y
1
-től legalább 4 távolságra csak
y
3
és
y
4
van, így ezek kell, hogy legyenek
y
1
x
-en kívüli további szomszédai.
Hasonlóan
y
2
szomszédos
y
4
-gyel és
y
5
-tel, és
y
3
szomszédos
y
5
-tel, azaz Petersen gráfot kapunk (80. ábra).
- 11. feladat F Ö
I. Először tegyük fel, hogy
g
páratlan. Legyen
x
0
∈
V
(
G
)
, és jelöljük
S
i
-vel az
x
0
-tól
i
i
=
0
,
…
,
g
−
1
2
i
távolságra lévő pontok halmazát.
S
i
minden
x
pontjából pontosan egy él megy
S
i
−
1
-be, hiszen két ilyen él két
x
-ből
x
0
-ba menő
i
hosszúságú utat eredményezne, és ezek
g
-nél rövidebb kört eredményeznének.
Tehát
S
i
+
1
=
(
r
−
1
)
⋅
S
i
i
=
1
,
…
,
g
−
2
3
, és így
II. Legyen
g
páros és tekintsünk két szomszédos
pontot,
x
-et és
y
-t. Jelöljük
S
i
-vel az
{
x
,
y
}
halmaztól
i
i
=
1
,
…
,
g
2
−
1
távolságra lévő pontok halmazát. Az
eredmény a fentihez hasonló számolással adódik.
[W. T. Tutte, P. Erdős–H. Sachs]
- 12. feladat F Ö
Tegyük fel, hogy már megkonstruáltuk
G
(
r
,
g
)
-t és
G
(
r
′
,
g
−
1
)
-t, ahol
r
′
=
V
(
G
(
r
,
g
)
)
. Osszuk fel
G
(
r
′
,
g
−
1
)
minden pontját
r
′
elsőfokú ponttá, és azonosítsuk ezt az
r
′
pontot
G
(
r
,
g
)
egy példányának pontjaival. A kapott
G
′
gráf nyilvánvalóan
(
r
+
1
)
-reguláris. Azt állítjuk, hogy a
kerülete
g
. Ha vesszük
G
(
r
,
g
)
egy példányának egy minimális körét,
annak hossza
g
; emiatt
G
′
kerülete legfeljebb
g
.
G
(
r
,
g
)
bármely példányának bármely más köre
legalább
g
hosszúságú. Legyen
C
egy
G
(
r
,
g
)
példányaiban nem szereplő
s
hosszúságú kör. Húzzuk össze
G
(
r
,
g
)
minden példányát, ekkor
G
′
-t leképeztük
G
(
r
′
g
−
1
)
-be.
C
egy nem üres, páros fokú részgráfba
képződik le, így
C
képe tartalmaz egy
C
′
kört. Tudjuk, hogy
C
G
(
r
,
g
)
legalább egy példányának legalább egy
élét tartalmazza[], és így
C
′
-nek
s
-nél kevesebb éle van. Tehát
s
−
1
≥
g
−
1
,
s
≥
g
. Így
G
′
=
G
r
+
1
,
g
.
Mivel
G
r
,
2
is és
G
2
,
g
is triviálisan létezik (rendre
r
párhuzamos él vagy egy
g
-szög), azt kapjuk, hogy
G
3
,
3
,
G
4
,
3
, …,
G
3
,
4
,
G
4
,
4
, …, ; …, ;
G
3
,
g
,
G
4
,
g
, … szintén léteznek.
[P. Erdős–H. Sachs].
- 13. feladat F Ö
(a) Indirekte tegyük fel, hogy
a
∈
V
G
és
b
∈
V
G
távolsága nagyobb, mint
g
. Hagyjuk el
a
-t és
b
-t, majd vegyünk fel új éleket, melyek
a
szomszédjait
b
szomszédjaival párosítják. A kapott
G
′
gráf nyilvánvalóan
r
-reguláris.
Megmutatjuk, hogy
G
′
kerülete legalább
g
. Legyen
C
egy
G
′
-beli kör. Ha
C
nem tartalmaz egyet sem az
r
új élből, akkor
C
egyben
G
egy köre is, és így hossza legalább
g
. Tehát tegyük fel, hogy
C
tartalmaz valahány új élt.
Tekintsünk egy (
G
−
{
a
,
b
}
)-beli
P
utat, mely az új élek közül két
végpontot köt össze. Ha
P
az
a
egy szomszédját
b
egy szomszédjával köti össze, akkor
mivel
a
és
b
távolsága legalább
g
+
1
,
P
hossza legalább
g
−
1
. Ha
P
az
a
(vagy a
b
) két szomszédját köti össze, akkor a
további élekkel együtt
G
egy
a
-n (vagy
b
-n) áthaladó körét alkotja, így hossza
legalább
g
−
2
.
Mármost ha
C
csak egy új élt tartalmaz, akkor akkor
tartalmaz egy utat, mely ezen él két végpontját köti
össze. A fenti érveléssel ez az út legalább
g
−
1
élből áll, így
C
legalább
g
hosszúságú.
Másrészről ha
C
legalább két új élt tartalmaz, akkor
tartalmaz legalább két utat is, melyek ezek végpontjait
kötik össze. Így a hossza legalább
Tehát
G
′
r
-reguláris, és kerülete legalább
g
. Mivel
V
G
′
<
V
G
, ez ellentmondás.
(b) I. Tegyük fel, hogy
r
=
2
l
. Legyen
x
∈
V
G
. Hagyjuk el
x
-et és párosítsuk a szomszédjait
l
darab új független éllel. Az így adódó
G
′
gráf nyilván
r
-reguláris. Mivel
V
G
′
<
V
G
,
G
′
kerülete kisebb kell, hogy legyen
g
-nél, azaz tartalmaznia kell egy
g
-nél rövidebb
C
kört. Természetesen
C
tartalmaz valahány (legalább egy) új
élt; legyenek ezek
e
1
,
…
,
e
s
, és osszák
C
-t a
P
1
,
…
,
P
s
ívekre. Azt tapasztaljuk, hogy
P
i
kört alkot
G
-ben, ha hozzávesszük azt a két új
élt, melyek a végpontjait
x
-szel kötik össze, tehát
E
P
i
≥
g
−
2
. Így
Tehát
s
=
1
, vagyis
C
egy
e
1
új élből és egy olyan, az
e
1
végpontjait összekötő
P
1
útból áll, melyre
P
1
⊆
G
−
{
x
}
. Az is következik, hogy
P
1
-nek
g
−
2
éle van, azaz végpontjait
x
-hez kötve egy
g
hosszúságú
G
-beli kört kapunk.
II. Tegyük fel, hogy
r
=
2
l
+
1
. Ha
f
=
2
vagy 3, akkor
G
rendre
r
párhuzamos élből áll, vagy
G
=
K
r
+
1
. Tehát feltehetjük, hogy
g
≥
4
.
Legyen
x
,
y
∈
E
G
. Hagyjuk el
x
-et és
y
-t
G
-ből és párosítsuk mind
x
, mind
y
megmaradó
2
l
szomszédját. Az így adódó
G
′
gráf ismét
r
-reguláris. Mivel
V
G
′
<
V
G
,
G
′
tartalmaz egy
g
-nél rövidebb
C
kört. Megint legyen
e
1
,
…
,
e
s
az új élek
C
-n, és osszák ezek
C
-t a
P
1
,
…
,
P
s
ívekre. Jegyezzük meg, hogy
Tehát
ami miatt
s
=
1
, minthogy
g
≥
4
. Levonhatjuk a korábbihoz hasonló
következtetést, hogy
P
1
-et tartalmazza
G
egy
g
hosszúságú köre, ami áthalad
x
-et vagy
y
-on.
(c) Legyen
x
∈
V
G
. (a) szerint
G
minden pontja elérhető
x
-ből egy legfeljebb
g
hosszúságú úton. De legfeljebb
≤
r
r
−
1
j
−
1
darab
j
hosszúságú,
x
-ből induló út van (lehet köztük
azonos végpontú; lehet köztük
x
-be visszatérő), és így
[uo.]
- 14. feladat F Ö
Vegyünk egy maximális
g
kerületű
G
′
gráfot, mely előáll
G
-ből független élek hozzávételével.
Indirekte tegyük fel, hogy
G
′
-ben van egy
r
fokú
u
pont. Ekkor paritás-megfontolások
miatt van egy másik ilyen
v
pontja is.
Legyen
S
a
G
′
azon pontjainak halmaza, melyek
{
u
,
v
}
-től
g
−
1
távolságra vannak.
G
′
minden
S
-en kívüli
w
pontjának foka
r
+
1
kell, hogy, legyen, különben az
u
,
w
élt hozzávehetnénk
G
′
-höz. Mivel a 10.11 megoldásában
szereplőhöz hasonló számítással azt kapjuk, hogy
az adódik, hogy van két
S
-en kívüli
x
és
y
pont, melyeket
E
G
′
−
E
G
egy éle köt össze. Így
G
′
−
x
,
y
+
x
,
u
+
x
,
v
egy legalább
g
kerületű gráf, mely
G
-ből független élek felvételével áll
elő, és
G
′
-nél nagyobb, ami ellentmondás.
- 15. feladat F Ö
(a) Legyen
U
a
G
F
p
feletti projektív tér pontjainak,
W
pedig az egyeneseinek halmaza. Kössük
össze
u
∈
U
-t
w
∈
W
-vel, ha
u
∈
w
. Az így adódó páros gráf könnyen
láthatóan
p
+
1
-reguláris, és
2
p
2
+
p
+
1
pontja van. Annak bizonyításához, hogy
kerülete 6, vegyük észre, hogy nem tartalmaz
négyszöget; valóban, ha
u
1
,
w
1
,
u
2
,
w
2
egy kör lenne, akkor a
w
1
és
w
2
egyeneseknek két közös
u
1
és
u
2
pontja lenne. Nem tartalmaz 3 és 5
hosszúságú kört sem, mert páros. (A tér minden
háromszöge a gráfban hatszöget ad.)
(b) Tekintsük az
F
=
{
x
:
x
T
x
=
0
}
hiperfelületet a
G
F
p
feletti 4-dimenziós projektív térben.
Először
F
néhány geometriai tulajdonságát
bizonyítjuk be.
(i)
F
nem tartalmaz síkot. Indirekte tegyük
fel, hogy
π
egy sík
F
-ben és legyen
u
,
v
∈
π
. Ekkor
u
T
u
=
0
,
v
T
v
=
0
és
u
+
v
T
u
+
v
=
0
(hiszen
u
,
v
és
u
+
v
π
pontjait reprezentáló vektorok). Ebből
az következik, hogy
u
T
v
=
0
. Így ha
V
a
π
pontjainak homogén koordináta-ötösei
által alkotott lineáris alteret jelöli az 5-dimenziós
vektortérben, akkor
V
⊆
V
⊥
. De ez azt jelentené, hogy
dim
V
⊥
≥
dim
V
=
3
, ami ellentmond 5.31-nek.
(ii)
F
-nek pontosan
p
+
1
egyenese halad át
F
minden
b
pontján. Legyen
Σ
=
{
x
:
b
T
x
=
0
}
az „érintő hipersík”
b
-ben.
Σ
minden
b
-n áthaladó egyenest tartalmaz; mert
ha
v
egy ilyen egyenes egy pontja, akkor
ugyanúgy, mint (i)-ben az következik, hogy
b
T
v
=
0
. Megfordítva, ha
v
∈
F
∩
Σ
, akkor a
b
és
v
által feszített egyenes minden pontját
tartalmazza
F
∩
Σ
.
Legyen
π
tetszőleges
Σ
-beli
b
-t nem tartalmazó sík. Ekkor
π
∩
F
egy kúpszelet, ami nem degenerált,
hiszen ha tartalmazna egy egyenest, akkor ez
b
-vel együtt egy
F
által tartalmazott teret adná,
ellentmondva (i)-nek. Így
π
∩
F
-nek
p
+
1
pontja van. Mármost az
F
-beli
b
-n áthaladó egyenesek pontosan azok,
melyek
b
-t
π
∩
F
pontjaival kötik össze, tehát ezekből
p
+
1
van.
Ezekből a megfontolások (i)-gyel együtt az is
következik, hogy nincsen három olyan egyenes
F
-ben, melyek háromszöget
alkotnak.
(iii)
F
=
p
3
+
p
2
+
p
+
1
. Vegyük észre, hogy ha adva van egy
tetszőleges
Λ
egyenes és egy tetszőleges
F
−
Λ
-ra eső
b
pont, akkor
F
-ben egyetlenegy olyan egyenes van,
mely tartalmazza
b
-t és metszi
Λ
-t. Valóban, a
b
-beli
Σ
érintő hipersík nem tartalmazhatja
Λ
-t, így
Σ
a
Λ
-t egyetlen
a
pontban metszi, és így az
a
b
egyenes egyértelmű. Így ha bármelyik
Λ
egyenest tekintjük, ezen
p
+
1
pont van, ezek mindegyikére
p
további egyenes illeszkedik, és
F
minden pontja ezen egyenesek közül
pontosan egyre illeszkedik. Így
F
−
Λ
=
p
2
p
+
1
, ami bizonyítja az állítást.
Mivel minden egyenes
p
+
1
pontot tartalmaz és minden pont
F
-nek
p
+
1
egyenesére illeszkedik,
F
egyeneseinek száma ugyanez. Jelöljük
F
egyeneseinek halmazát
L
-vel.
Alkossunk páros gráfot
F
∪
L
-en úgy, hogy akkor és csak akkor
kötjük össze
b
∈
F
-t
Λ
∈
L
-vel, ha
b
∈
Λ
. A kapott páros gráf (ii) szerint
p
+
1
-reguláris, és (iii) szerint
2
p
3
+
p
2
+
p
+
1
pontja van. Nem tartalmaz sem 4, sem 6
hosszúságú kört, mivel egy 4 hosszúságú kör
F
két olyan egyenesének felelne meg,
melyek két pontban metszik egymást, egy 6 hosszúságú
kör pedig
F
három háromszöget alkotó egyenesének;
mindkettő lehetetlen.
- 16. feladat F Ö
(a) Ha
Z
az összes kört lefogja, akkor
V
G
−
Z
erdőt feszít, és így legfeljebb
n
−
Z
−
1
élt feszít. Mivel minden pont foka
legalább 3,
V
G
−
Z
pontjait
3
n
−
Z
él hagyja el. Ezen halmaz által
feszített éleket itt kétszer számoltuk, de így is
legalább
él köti
V
G
−
Z
-t
Z
-hez. Másrészről
Z
egy pontja nem több mint
d
élhez illeszkedik, így a
V
G
−
Z
,
Z
élek száma legfeljebb
d
⋅
Z
. Tehát
vagy ezzel ekvivalens formában
(b) Feltehetjük, hogy
g
≥
3
, minthogy a
g
=
1
és 2 eset triviális.
Legyen
d
a
G
-beli maximális fokszám. Ugyanolyan
leszámlálással, mint 10.11-ben, azt kapjuk, hogy
Mármost (a) szerint bármely minden kört
lefogó
Z
halmaz eleget tesz a következőnek:
[H.–J. Voß, M. Simonovits]
- 17. feladat F Ö
Legyen
G
1
,
G
2
,
…
,
G
ν
az ötlettár szerint definiálva;
G
ν
+
1
=
∅
. Feltehetjük, hogy minden
G
i
kerülete legfeljebb
g
, különben tekinthetnénk
G
helyett
G
i
-t. Így
V
C
1
∪
…
∪
V
C
ν
≤
ν
g
.
Másrészről könnyen ellenőrizhető, hogy
V
C
1
∪
…
∪
V
C
ν
a
G
gráf minden körét lefogja. Tehát az
előző fejezet (b) része azt adja, hogy
Így
mint azt állítottuk. [uo.]
- 18. feladat F Ö
(a)
ν
=
1
azt jelenti, hogy
G
bármely két körének van közös pontja.
Ha
G
nem egyszerű, azaz tartalmaz hurokélt
vagy két párhuzamos élt, akkor minden kört lefog rendre
1 vagy 2 pont. Így feltehetjük, hogy
G
egyszerű. Ekkor 10.4 szerint
G
a 8. ábrán látható gráfok egyike.
K
5
köreit bármely 3 pontja lefogja; egy
kerék pontjait lefogja a középpont és a perem bármely
pontja; a harmadik példát (
K
3
,
n
−
3
a 3 elemű osztályhoz néhány él
hozzávételével) lefogja a 3 elemű osztály bármely két
pontja. [Bollobás B., Pósa L.]
(b) Indukciót alkalmazunk
V
G
-re. Feltehetjük, hogy
G
-nek nincsen sem első-, sem másodfokú
pontja, mert ezeket rendre elhagyhatnánk, illetve
„kisimíthatnánk”. Hagyjuk el egy legrövidebb kör
pontjait. 10.16b szerint ennek hosszára fennáll
Jelölük
τ
′
-vel a megmaradó gráf összes körének
lefogásához szükséges pontok minimális számát.
Nyilvánvaló, hogy
Így felhasználva az indukciós feltevést,
(c) Legyen
G
3-reguláris,
g
kerületű gráf minimális
n
pontszámmal. 10.13c-ból
10.16a szerint legalább
n
∕
4
pont kell minden kör lefogásához, azaz
n
≤
4
τ
. Továbbá
[Erdős P.–Pósa L.; l. még H.–J. Voß,
Theory of Graphs (Akadémiai Kiadó, Budapest 1968) és
M. Simonovits, Acta Math. Acad. Sci. Hung.
18
(1967), 191–206.]
- 19. feladat F Ö
G
1
=
G
−
x
-et tekintjük. Mivel
G
2-szeresen összefüggő,
G
1
összefüggő.
1
∘
Ha
G
1
2-szeresen összefüggő, akkor legyen
x
1
tetszőleges
x
-gyel szomszédos pont. Mivel
d
G
1
≥
k
−
1
minden
z
≠
x
1
,
y
-ra (valójában minden
z
≠
y
-ra), van
G
1
-ben legalább
k
−
1
hosszúságú
x
1
,
y
-út.
x
,
x
1
-et hozzávéve egy legalább
k
hosszúságú
x
,
y
-utat kapunk.
2
∘
Tegyük fel, hogy
G
1
nem 2-szeresen összefüggő és legyen
G
1
=
A
∪
B
,
V
A
∩
V
B
=
1
. A jelöléseket válasszuk úgy, hogy
y
∈
V
A
és tegyük fel, hogy
B
minimális. Ekkor
B
nyilvánvalóan 2-szeresen összefüggő.
Legyen
{
y
1
}
=
V
B
∩
V
A
. Tekintve, hogy
G
2-szeresen összefüggő,
x
-nek szomszédosnak kell lenni egy
x
1
∈
V
B
−
{
y
1
}
ponttal.
Mármost
B
minden
z
≠
y
1
pontjának foka legalább
k
−
1
, így
B
tartalmaz egy legalább
k
−
1
hosszúságú
P
1
utat
x
1
és
y
1
között. Legyen továbbá
P
2
egy
A
-beli
y
1
,
y
-út; ekkor
egy legalább
k
hosszúságú
x
,
y
-út
G
-ben.
- 20. feladat F Ö
Legyen
X
az ötlettár szerint definiálva.
Nyilvánvaló, hogy a
P
ismételt deformációjával előálló utak
pontjai azonosak, tehát
X
⊆
V
P
. Legyen
X
=
{
x
0
,
x
i
1
,
…
,
x
i
t
,
x
m
}
(
0
<
i
1
<
…
<
i
t
<
m
). Azt állítjuk, hogy
(ami miatt
Γ
X
−
X
≤
2
t
+
2
=
2
X
−
2
).
Legyen
u
∈
Γ
X
,
u
∉
X
. Ekkor
u
szomszédos egy
v
∈
X
ponttal. Mivel
v
definíció szerint végpontja egy olyan
maximális útnak, melynek pontjai
P
pontjai,
u
-nak rajta kell lenni
P
-n. Legyen
u
=
x
i
.
A
v
pont definíciója szerint vannak olyan
P
0
=
p
,
P
1
,
…
,
P
s
utak, hogy
P
j
+
1
előáll
P
j
deformációjával (
j
=
0
,
…
,
s
−
1
), és
v
végpontja
P
s
-nek. Ha mind az
x
i
,
x
i
−
1
, mind az
x
i
,
x
i
+
1
él végpontja egy
P
s
-ből deformációval előálló útnak,
akkor legyen mondjuk
x
i
,
x
i
+
1
a
P
s
u
,
v
-ívének első éle. Ekkor
x
i
+
1
végpontja egy
P
s
-ből deformációval előálló útnak, azaz
x
i
+
1
∈
X
és készen vagyunk.
Így tegyük fel, hogy pl.
x
i
+
1
,
x
i
∉
E
P
s
. Ekkor van egy
j
index (
0
≤
j
≤
s
−
1
), melyre
x
i
+
1
,
x
i
∈
E
P
j
, de
x
j
+
1
,
x
i
∉
E
P
j
+
1
. Mivel
P
j
+
1
előáll
P
j
-ből deformációval, ez csak akkor
lehetséges, ha
x
i
+
1
és
x
i
egyike végpontja
P
j
+
1
-nek. Mivel
x
i
∉
X
, ezért
x
i
+
1
∈
X
kell, hogy legyen, és ismét készen
vagyunk.
Tehát tudjuk, hogy
ami miatt a feltevésből azt kapjuk, hogy
X
≥
k
+
1
. Legyen
X
1
⊂
X
,
X
1
=
k
. Ekkor a feltevés szerint
és mivel
az adódik, hogy
Az állítás minden
k
-ra éles, amint azt bármely olyan gráf
mutatja, mely diszjunkt teljes
3
k
−
1
-szögekből áll. [L. Pósa,
Discrete Math. 14 (1976) 359–364].
- 21. feladat F Ö
(a) Indirekte tegyük fel, hogy
G
-ben nincsen Hamilton kör. Vegyünk fel
éleket
G
-ben addig, amíg ezzel nem hozunk
létre Hamilton kört. Mivel az (a) feltétel érvényes
marad (egyébként (b), (c) és (d) is), feltehetjük, hogy
G
már telített, azaz tetszőleges új él
felvételével Hamilton kör keletkezne. Legyen
x
,
y
∉
E
G
, és
H
a
G
+
x
,
y
Hamilton-köre. Ekkor
G
tartalmaz egy
x
-et
z
-vel összekötő
P
=
z
1
=
x
,
z
2
,
…
,
z
n
=
y
Hamilton-utat.
Legyenek
z
i
1
,
…
,
z
i
k
az
x
szomszédai
P
-n,
2
=
i
1
<
i
2
<
…
<
i
k
≤
n
. Ekkor
y
nem lehet szomszédos
z
i
ν
−
1
-gyel (
1
≤
ν
≤
k
); különben
z
1
,
…
,
z
i
ν
−
1
,
z
n
,
z
n
−
1
,
…
,
z
i
ν
Hamilton kör lenne. Így
ami ellentmondás.
Most azt tegyük fel, hogy (d) áll fenn. Ismét
feltehetjük, hogy
G
nem tartalmaz Hamilton kört, de
bármely két nem szomszédos pontját egy éllel összekötve
már igen. Legyen
x
k
,
x
l
egy nem szomszédos pár, melyre
k
+
l
maximális (
k
<
l
).
Ekkor
x
k
szomszédos
x
l
+
1
,
…
,
x
n
-nel, így
azt is tudjuk, hogy
x
l
szomszédos
x
k
+
1
,
…
,
x
l
−
1
,
x
l
+
1
,
…
,
x
n
-nel, azaz
Az (a)-hoz hasonló érvelés azt adja, hogy
(2)-ből és (3)-ból
Legyen
m
=
d
k
. Ekkor (4) szerint
m
≤
k
, és így
d
m
≤
d
k
=
m
. Ezen kívül (3)-ból az következik,
hogy
Tehát a feltevés szerint
Innen az adódik, hogy
vagy, ami ezzel ekvivalens
ami ellenmond (1)-nek.
Ha (b) fennáll, akkor nyilvánvaló, hogy (d) is
fennáll. Tegyük fel, hogy (c) fennáll, és legyen
d
k
≤
k
<
n
2
,
l
=
n
−
k
. Ekkor (c) szerint vagy
d
l
≥
l
, vagy
d
k
+
d
l
≥
l
+
k
=
n
, ami miatt
d
l
>
l
. Tehát (d) ismét fennáll, és így egy
Hamilton kör létezése következik.
- 22. feladat F Ö
Legyen
G
olyan egyszerű gráf, amely nem
tartalmaz
F
élein áthaladó Hamilton kört.
Feltehetjük, hogy
G
-hez bármely élt hozzávéve már van
ilyen Hamilton kör (mert a
V
G
-n értelmezett teljes gráfban van egy
F
-en áthaladó Hamilton kör, minthogy
F
diszjunkt utakból áll). Legyen
x
,
y
∉
E
G
. Ekkor van
G
+
x
,
y
-ben
F
-en áthaladó Hamilton kör, azaz van
G
-ben egy
F
-en áthaladó,
x
-et
y
-nal összekötő
P
Hamilton út. Legyen
P
=
x
=
z
1
,
z
2
,
…
,
z
n
=
y
. Legyen
x
szomszédos
z
i
1
,
…
,
z
i
k
-val (
2
=
i
1
<
…
<
i
k
<
n
). Mint korábban is, itt is
következik, hogy
z
i
ν
−
1
(
1
≤
ν
≤
k
) csak akkor lehet szomszédos
y
-nal, ha
z
i
ν
−
1
,
z
i
ν
∈
F
. Tehát legfeljebb
n
−
1
−
k
+
q
pont szomszédos
y
-nal. Így
Ez nyilvánvalóan lehetetlen.
Megjegyzés: Hasonló általánosítást fogalmazhatunk
meg, mint az előző feladatban.
- 23. feladat F Ö
Vegyünk fel egy
y
pontot és kössük össze minden más
ponttal. A kapott
2
n
+
2
pontú gráfban minden pont foka
legalább
n
+
1
, és Dirac tétele (10.21a) szerint van
benne Hamilton kör.
y
-t elhagyva még mindig van egy
x
0
,
…
,
x
2
n
Hamilton út
G
-ben. Tegyük fel, hogy
G
-ben nincs Hamilton kör, ekkor a
következő szabály fogalmazható meg:
ha
x
0
szomszédos
x
i
-vel, akkor
x
2
n
szomszédos
x
i
−
1
-gyel.
Mivel
x
0
és
x
2
n
fokszáma is
n
, fenn kell állni annak, hogy ha
x
0
nem szomszédos
x
i
-vel, akkor
x
2
n
szomszédos
x
i
−
1
-gyel.
Először tegyük fel, hogy
x
0
szomszédos
x
1
,
…
,
x
n
-nel és
x
2
n
szomszédos
x
n
,
…
x
2
n
−
1
-gyel. Van olyan
i
,
1
≤
i
≤
n
, melyre
x
i
nem szomszédos
x
n
-nel; ekkor
x
i
szomszédos
x
j
-vel valamely
n
<
j
≤
2
n
−
1
-re, mert
d
G
n
=
n
. Ekkor az
x
i
,
x
i
−
1
,
…
,
x
0
,
x
i
+
1
,
…
,
x
j
−
1
,
x
2
n
,
…
,
x
j
kör Hamilton kör (81. ábra).
Legyen
1
≤
i
≤
2
n
−
1
olyan, hogy
x
i
+
1
szomszédos
x
0
-lal, de
x
i
nem. A fenti érvelés szerint
x
i
−
1
szomszédos
x
2
n
-nel. Tehát
G
tartalmaz egy
2
n
hosszúságú
x
i
−
1
,
…
,
x
0
,
x
i
+
1
,
…
,
x
2
n
kört.
Legyen
C
=
y
1
,
…
,
y
2
n
egy
2
n
hosszúságú kör
G
-ben és legyen
y
0
az utolsó pont. Mivel
C
maximális kör
G
-ben,
y
0
nem lehet szomszédos
C
két egymás melletti pontjával; így
C
minden második pontjával kell, hogy
szomszédos legyen, mondjuk
y
1
,
y
3
,
…
,
y
2
n
−
1
-gyel.
y
2
i
-t
y
0
-val helyettesítve egy másik maximális
kört kapunk, és így
y
2
i
is szomszédos kell, hogy legyen
y
1
,
y
3
,
…
,
y
2
n
−
1
-gyel. Így
y
1
szomszédos
y
0
,
y
2
,
…
,
y
2
n
-nel, azaz
ami ellentmondás.
[C. St. J. A. Nash-Williams,
Proc. Amer. Math. Soc.
17 (1966), 466–467.]
- 24. feladat F Ö
Legyen
x
,
y
∈
V
G
, bebizonyítjuk, hogy összeköthetők
Hamilton úttal. Feltehetjük, hogy
x
,
y
∈
E
G
, mivel ha
x
-et és
y
-t egy új éllel összekötjük, az sem a
feltételt, sem a következményt nem befolyásolja.
Osszuk fel az
x
,
y
élt egy új
z
ponttal. Ekkor könnyen igazolható,
hogy a kapott
G
′
gráfban akkor és csak akkor van
Hamilton kör, ha
G
tartalmaz egy
x
-et
y
-nal összekötő Hamilton utat.
Mármost
G
′
fokszámaira
ahol
d
2
≤
…
≤
d
n
+
1
a
G
fokszámai; így
d
2
≥
n
+
1
2
a feltétel szerint. Mivel
V
G
′
=
n
+
1
, a Pósa feltétel (10.21b) ki van
elégítve, és így
G
′
-ben van Hamilton kör. Tehát
G
tartalmaz
x
-et
y
-nal összekötő Hamilton utat.
- 25. feladat F Ö
Legyen
C
=
x
1
,
…
,
x
m
egy leghosszabb irányított kör
G
-ben. Ekkor
V
C
>
n
2
. Valóban, legyen
Q
=
z
0
,
…
,
z
p
egy leghosszabb (irányított) út és
z
i
1
,
…
,
z
i
k
(
i
1
<
…
<
i
k
) a
G
azon pontjai, melyekre
z
i
ν
,
z
0
∈
E
G
(ezek nyilvánvalóan
Q
-n helyezkednek el). Ekkor
i
k
≥
k
≥
n
∕
2
, és így a
z
0
,
…
,
z
i
k
irányított kör hossza
>
n
∕
2
.
Tegyük fel, hogy
C
nem irányított Hamilton kör és legyen
P
=
y
0
,
…
,
y
l
egy leghosszabb
G
−
V
C
-beli út.
u
,
y
0
∈
E
G
legalább
n
2
−
l
nem
P
-beli
u
pontra. Ezen pontok mindegyike
C
-n van; jelöljük őket
x
i
1
,
…
,
x
i
t
-vel,
t
≥
n
2
−
l
. Hasonlóan vannak olyan
x
j
1
,
…
,
x
j
s
pontok,
s
≥
n
2
−
l
, melyekre
y
l
,
x
j
ν
∈
E
G
,
1
≤
ν
≤
s
.
Vegyük észre, hogy ha
x
i
ν
≠
x
i
μ
, akkor
C
x
i
ν
,
x
i
μ
íve legalább
l
+
2
hosszú kell, hogy legyen, hiszen
különben
C
ezen ívét
x
i
ν
,
y
0
+
P
+
y
l
,
x
j
μ
-vel helyettesíthetnénk. Tehát ha
vesszük
C
egy
x
i
ν
+
1
-ben (
x
m
+
1
=
x
1
) induló
l
hosszúságú (
1
≤
ν
≤
t
)
A
ν
ívét, akkor
De könnyen látszik, hogy
⋃
ν
=
1
t
V
A
n
≥
t
+
l
, és így
s
≤
m
−
t
+
l
, vagy, ami ezzel ekvivalens,
De
P
-nek
n
−
m
-ből
l
+
1
pontja van, tehát
ami ellentmondás. [C. St. J. A.
Nash-Williams]
- 26. feladat F Ö
Legyen
C
maximális kör
G
-ben. Indirekte tegyük fel, hogy
C
nem Hamilton kör. Ekkor
G
−
V
C
nem üres; legyen
G
1
egy komponense. Legyenek
x
1
,
…
,
x
s
a
C
kör
G
1
-gyel szomszédos pontjai. Vegyük
észre, hogy
C
maximalitása miatt az
x
i
-k között nincsen két olyan, melyek
C
-n szomszédosak. Ebből az következik,
hogy
{
x
1
,
…
,
x
s
}
elválasztja
G
-t, és így
s
≥
k
.
C
-n egy adott irányban végighaladva
legyen
y
1
,
…
,
y
s
az
x
1
,
…
,
x
s
-et következő pontok.
Azt állítjuk, hogy
y
1
,
…
,
y
s
függetlenek. Tegyük fel, hogy
y
i
és
y
j
szomszédosak, ekkor hagyjuk el
x
i
,
y
i
-t és
x
j
,
y
j
-t
C
-ből és vegyük hozzá
y
i
,
y
j
-t és egy
G
1
-en áthaladó
x
i
,
x
j
utat; az így előálló kör hosszabb
C
-nél, ami ellentmondás.
Az is belátható, hogy nincsen olyan
y
i
, mely szomszédos
G
1
-gyel, és így egy
y
0
∈
V
G
1
-et választva az
S
=
{
y
0
,
y
1
,
…
,
y
s
}
halmaz független lesz. De
ami ellentmondás.
[P. Erdős–V. Chvátal]
- 27. feladat F Ö
(a) Legyen
P
=
x
0
,
x
1
,
…
,
x
m
egy leghosszabb út. Ekkor
x
0
minden szomszédja rajta van
P
-n; mivel
d
G
x
0
≥
k
, ezen szomszédok egyike olyan
x
i
, melyre
k
≤
i
≤
m
. Ekkor
C
=
x
0
,
…
,
x
i
egy
i
+
1
≥
k
+
1
hosszúságú kör.
(b) Legyen
P
úgy, mint fent, egy leghosszabb út.
Először tegyük fel, hogy léteznek olyan
x
i
és
x
j
pontok, hogy
i
<
j
,
x
i
szomszédos
x
m
-mel,
x
j
pedig
x
0
-lal. Feltehetjük, hogy
j
−
i
minimális az ilyen indexpárok között.
Legyen
C
=
c
0
,
…
,
x
i
,
x
m
,
x
m
−
1
,
…
,
x
j
. Ha
j
=
i
+
1
, akkor
C
hossza
m
+
1
, és Hamilton kör kell, hogy legyen,
mivel különben lenne
C
-n kívül olyan
C
-vel szomszédos pont, mely
P
-nél hosszabb utat eredményezne. Így
feltehetjük, hogy
j
≥
i
+
2
. Ekkor
x
i
+
1
,
…
,
x
j
−
1
nem szomszédosak sem
x
0
-lal, sem
x
m
-mel, így
C
tartalmazza
x
m
-et,
x
m
minden szomszédját és minden olyan
x
ν
pontot, melyre
x
ν
+
1
szomszédos
x
0
-lal, kivéve
x
j
−
1
-et. Ezen pontok különbözőek, emiatt
C
hossza legalább
2
k
.
Tehát tegyük fel, hogy az utolsó
x
0
-lal szomszédos
x
i
pont előbb van az első
x
m
-mel szomszédos
x
j
pontnál (esetleg
x
i
=
x
j
). Mivel
G
2-szeresen összefüggő, két független
út,
P
1
és
P
2
köti össze a
C
1
=
x
0
,
…
,
x
i
és
C
2
=
x
j
,
…
,
x
m
köröket. Feltehetjük, hogy egyikük
x
i
-ből indul; hiszen különben addig
sétálhatnánk az
x
i
,
…
,
x
j
úton, amíg vagy
C
2
-t, vagy
P
ν
-t elérjük, és helyettesíthetnénk
P
ν
egy megfelelő darabját ezzel az úttal.
Hasonlóan azt is feltehetjük, hogy
P
1
és
P
2
egyike
x
j
-ben végződik. Lehetséges, hogy
ugyanaz a
P
ν
x
i
-ben végződik, és az is, hogy nem; de
mindkét esetben olyan kört kapunk, mely tartalmazza
x
0
-t,
x
m
-et, és ezek minden szomszédját, mint
azt a 82. ábra mutatja. E kör hossza nagyobb
2
k
-nál. [G. A. Dirac, Proc. London Math.
Soc. 2 (1952) 69–81]
- 28. feladat F Ö
Ha
G
-nek van egy legfeljebb
k
∕
2
fokú
x
pontja, akkor
G
−
x
-ben
n
−
2
k
2
-nél több él van, és így az indukciós
feltevés szerint
G
−
x
tartalmaz egy
k
-nál hosszabb kört. Tehát feltehetjük,
hogy
G
minden pontjának foka legalább
k
+
1
2
.
Azt is megállapítjuk, hogy ha
G
nem 2-szeresen összefüggő, mondjuk
G
=
G
1
∪
G
2
és
V
G
1
∩
V
G
2
≤
1
, akkor
miatt az következik, hogy
i
=
1
vagy 2-re
és az indukció ismét alkalmazható. Tehát
feltehetjük, hogy
G
2-szeresen összefüggő. Ekkor 10.27-ből
az adódik, hogy
G
tartalmaz egy legalább
k
+
1
hosszúságú kört.
Az állítás éles minden olyan gráfra, melynek
tagjai teljes
k
-szögek. [P. Erdős
P.–T. Gallai, Acta
Math. Acad. Sci. Hung.
10 (1959),
337–356]
- 29. feladat F Ö
Legyen
P
=
0
,
1
,
…
,
N
tetszőleges
G
-beli út. Legyen
R
1
egy
P
,
P
-út olyan
i
1
=
0
és
j
1
végpontokkal, melyekre
j
1
maximális. Tegyük fel, hogy az
R
1
,
…
,
R
k
P
,
P
-utakat már kiválasztottuk,
R
ν
végpontjaira
i
ν
<
j
ν
és
j
k
<
N
. Legyen
R
k
+
1
egy
{
0
,
…
,
j
k
−
1
}
-et
{
j
k
+
1
,
…
,
N
}
-nal összekötő
P
,
P
-út (ilyen út létezik, mert
G
2-szeresen összefüggő), és legyen
R
k
+
1
-nek az utóbbi halmazbeli
j
k
+
1
végpontja a lehető legnagyobb. Ha
j
k
=
N
, megállunk; legyen
s
a
k
ezen értéke.
A definícióból következik, hogy
Az is igaz, hogy
hiszen ellenkező esetben
R
k
+
1
-t választhattuk volna
R
k
helyett. Tehát
Hasonló érveléssel belátható, hogy
R
1
,
…
,
R
s
független utak. Így
P
∪
R
1
∪
…
∪
R
s
az ötlettárban leírt
struktúrájú.
Tegyük fel, hogy
s
=
2
p
+
1
páratlan (a páros eset hasonlóan
kezelhető, így az olvasóra bízzuk). Ekkor az
i
p
+
1
és
j
p
+
1
közti ív nem hosszabb
l
−
1
-nél, hiszen
R
p
+
1
-gyel kört alkot. Hasonlóan
P
i
p
,
i
p
+
1
-íve és
j
p
+
1
,
j
p
+
2
-íve kört alkot
R
p
,
R
p
+
1
,
R
p
+
2
-vel és
P
j
p
,
i
p
+
2
-ívével (ez utóbbi degenerálódhat; 83.
ábra), és így összhosszuk legfeljebb
l
−
3
. Hasonlóan kapjuk azt, hogy az
i
q
,
i
q
+
1
-ív és a
j
2
p
+
1
−
q
,
j
2
p
+
2
−
q
-ív hosszának összege legfeljebb
l
−
p
+
1
−
q
. Tehát
ami bizonyítja az állítást. [H.-J. Voß,
G. Dirac]
- 30. feladat F Ö
Legyen
x
,
y
∈
V
G
,
x
,
y
∈
E
G
. Bármely
z
∈
V
G
−
{
x
,
y
}
x
és
y
közül legfeljebb az egyikkel
szomszédos. Így
Adjuk össze ezt minden
x
,
y
élre, ekkor minden
d
x
pontosan
d
x
-szer szerepel a bal oldalon, azaz
Itt
tehát
[W. Mantel, Wiskundige Opgaven 10
(1906) 60–61. Más egyszerű bizonyításokat kapunk a
Turán tétel megoldásainak (10.34 és 10.35)
specializációjával.]
- 31. feladat F Ö
Legyen
x
a
G
tetszőleges pontja. Ekkor nincsen
x
-nek két olyan szomszédja, melyek
szomszédosak lehetnének, így
Legyen
S
be a
G
egy minimális pont-lefogása. Ekkor
G
minden élét reprezentálja
S
egy pontja, tehát
Mivel
az előző feladat eredménye ebből is
következik.
- 32. feladat F Ö
Nevezzünk egy
{
x
,
y
,
z
}
hármast rossznak, ha nem feszít
háromszöget sem
G
-ben, sem
G
¯
-ben. Ekkor az olyan rossz hármasok
száma, melyek által feszített élek közül pontosan egy
tartalmazza az
x
pontot
d
x
n
−
1
−
d
x
, így
a rossz hármasok számának kétszerese. Emiatt
G
és
G
¯
háromszögeinek száma együtt
(a) Ha
G
k
-reguláris, ez a formula a következő
egyszerűbb alakot ölti:
mint azt állítottuk.
(b) Tudjuk, hogy
és így
G
és
G
¯
háromszögeinek száma legalább
Megjegyzés: Ez
n
>
5
-re pozitív, ami Ramsey tételének (14.
fejezet) egy nagyon speciális esete.
[A. W. Goodman, Amer. Math. Monthly
66 (1959), 778–783.]
- 33. feladat F Ö
Legyen
x
,
y
∈
E
G
. Ekkor legalább
d
x
+
d
y
−
n
pont szomszédos
x
-szel és
y
-nal is, azaz legalább ennyi háromszög
tartalmazza
x
,
y
-t. Így
a háromszögek számát alulról becsli. Mivel
ebben a szummában
d
x
pontosan
d
x
-szer fordul elő,
G
háromszögeinek a száma legalább
A Cauchy–Schwartz egyenlőtlenség szerint ez
legalább
[uo.]
- 34. feladat F Ö
Indukciót alkalmazunk
m
-re. Ha
m
=
1
, az állítás nyilvánvaló.
Legyen
H
egy teljes
k
-szög
G
-ben (ilyen részgráf
k
szerinti indukció miatt létezik, vagy
„telíthetjük”
G
-t új élek felvételével addig, amíg
nem keletkezik teljes
k
+
1
-szög, és tekinthetjük
G
helyett a telített gráfot). Ha
G
nem tartalmaz teljes
k
+
1
-szöget, akkor minden
x
∈
V
G
−
V
H
a
H
gráfnak nem több mint
k
−
1
pontjával szomszédos. Így a
G
1
=
G
−
V
H
gráfban több mint
él van. Az indukciós feltevés szerint ebből
az következik, hogy
G
1
tartalmaz teljes
k
+
1
-szöget, gráfot, és így
G
is.
Az egyenlőséget akkor érjük el, ha
V
G
=
V
1
∪
…
∪
V
k
,
V
i
=
m
és két pont akkor és csak akkor
szomszédos, ha különböző
V
j
halmazba tartoznak.
Ha
n
=
m
k
+
r
, akkor azt állítjuk, hogy egy
háromszögmentes egyszerű gráfban akkor van a legtöbb
él, ha
G
=
H
n
,
k
,
V
H
n
,
k
=
V
1
∪
…
∪
V
k
,
V
1
=
…
=
V
r
=
m
+
1
,
V
r
+
1
=
…
=
V
k
=
m
, és két pont megint akkor és csak
akkor szomszédos, ha különböző osztályba tartoznak.
Ezen élszám
Ez az állítás
m
=
0
-ra triviálisan igaz és
m
szerinti indukcióval a fentivel azonos
módon bizonyítható. [Turán P.]
- 35. feladat F Ö
Legyen
x
maximális fokú pont és jelölje
G
0
az
x
szomszédai által feszített részgráfot.
Ekkor
V
G
0
-on van egy olyan
H
0
részgráf, mely
k
−
1
-kromatikus és eleget tesz a
következőknek:
ez
k
szerinti indukcióval adódik, mivel
G
0
nem tartalmaz teljes
k
-szöget.
H
-t definiáljuk
V
G
-n úgy, hogy a
H
0
élein kívül
V
G
−
V
G
0
minden pontját
G
G
0
minden pontjával összekötjük.
H
nyilvánvalóan
k
-kromatikus. Azt is tudjuk, hogy
Vegyük észre, hogy Turán tétele közvetlen
következmény. Hiszen legyenek
A
1
,
…
,
A
k
a
H
szín-osztályai,
A
i
=
a
i
. Ekkor
a
1
+
…
+
a
k
=
n
és
A jobb oldal akkor maximális, ha az
a
i
-k annyira közel vannak egymáshoz,
amennyire ez lehetséges; azaz
a
1
=
…
=
a
r
=
m
+
1
,
a
r
+
1
=
…
=
a
k
=
m
. Ez Turán korlátját adja. [Erdős Pál,
Mat. Lapok
21 (1970), 249–251]
- 36. feladat F Ö
(a) Tegyük fel, hogy
G
egyszerű
n
pontú gráf, mely nem tartalmaz 4
hosszúságú kört. Számoljuk meg azokat az
{
x
,
y
}
pontpárokat, melyekből mindkét pont
szomszédos ugyanazzal a harmadik
z
ponttal.
Egy rögzített
z
-re
d
z
2
ilyen párt számolunk. Másrészről
minden
{
x
,
y
}
párt legfeljebb egyszer számoltunk,
hiszen ha
z
1
-nél és
z
2
-nél is számbavettük volna, akkor
x
,
z
1
,
y
,
z
2
négyszöget alkotna. Tehát
Itt a Jensen-egyenlőtlenség miatt
és így
ami miatt
(b) Legyenek
V
G
pontjai a
G
F
p
fölött értelmezett projektív tér
pontjai, és az
[
x
,
y
,
z
]
és
[
u
,
v
,
w
]
pontokat akkor és csak akkor kössük
össze, ha
x
u
+
y
v
+
z
w
=
0
(ez azt jelenti, hogy akkor kötjük
őket össze, ha a
x
2
+
y
2
+
z
2
=
0
kúpszeletre nézve konjugáltak; homogén
koordinátákat használunk).
Bármely adott
u
ponttal szomszédos pontok a geometria
egy egyenesét alkotják (
u
polárisát), mely akkor és csak akkor
halad át
u
-n, ha
u
rajta van a
x
2
+
y
2
+
z
2
=
0
kúpszeleten. Így
G
-nek
p
+
1
pontja
p
fokú, és a maradék
p
2
pont foka
p
+
1
. Tehát
Másrészről
G
nem tartalmaz 4 hosszúságú kört.
Valóban, ha
u
és
v
két pont, akkor polárisaik egyetlen
pontban találkoznak (mivel triviálisan különböző
egyenesek), így bármely két pontnak legfeljebb egy
közös szomszédja van. [I. Reiman, Acta
Math. Acad. Sci. Hung.
9 (1959),
269–279.]
- 37. feladat F Ö
Legyen
m
=
E
G
,
V
G
=
{
x
1
,
…
,
x
n
}
,
d
G
x
i
=
d
i
. Mivel
G
nem tartalmaz
K
r
,
r
-t,
V
G
bármely adott
r
-esét legfeljebb
r
−
1
pont szomszédsága tartalmazza.
x
i
szomszédsága
d
i
r
r
-est tartalmaz. Tehát
A bal oldalt a Jensen-egyenlőtlenséggel
próbáljuk alulról becsülni. Sajnos
x
r
csak az
x
≥
r
−
1
esetben konvex. De legyen
ekkor
f
x
konvex, és mivel
d
i
egész, azt kapjuk, hogy
Mármost ha
2
m
n
<
r
−
1
, akkor nincs mit bizonyítanunk.
Tegyük fel, hogy
2
m
n
≥
r
−
1
, ekkor
Így
tehát
[K. Zarankiewicz problémája;
T. Kővári–V. T. Sós–P. Turán,
Colloqu. Math.
3 (1954), 50–57.]
- 38. feladat F Ö
(a) Indukciót alkalmazunk
k
-ra. Ha
k
=
1
, akkor az állítás igaz. Legyen
k
≥
2
és
s
=
1
ɛ
t
. Ha
n
elég nagy, akkor az indukciós feltétel
szerint találunk
k
diszjunkt
s
elemű halmazt,
A
1
,
…
,
A
k
-t, melyekre bármely két különböző
A
i
halmazba tartozó pont
szomszédos.
Jelölje
W
azon
U
=
V
G
−
A
1
−
…
−
A
k
-beli pontok halmazát, melyek minden
A
i
legalább
t
pontjával szomszédosak. Ekkor legalább
él hiányzik
U
és
A
1
∪
…
∪
A
k
között. Másrészről legfeljebb
1
k
−
ɛ
él hiányzik egy adott pontból, és így
legfeljebb
él hiányzik
U
és
A
1
∪
…
∪
A
k
között. Tehát
ami miatt
Tehát ha
n
nagy, akkor
W
is nagy lesz.
Válasszunk minden
w
∈
W
-hez minden
A
i
-ből
t
darab
w
∈
W
-vel szomszédos pontot. Ha
akkor szükségszerűen ugyanazt a
t
-est választjuk
t
különböző
W
-beli ponthoz. De ezen
t
pont a hozzájuk tartozó
k
t
-essel együtt egy keresett teljes
páros részgráfot alkot.
(b) Hagyjunk el egy pontot, melynek foka kisebb
mint
1
−
1
k
+
ɛ
2
⋅
V
G
(ha van ilyen); az így kapott
részgráffal tegyük ugyanezt, stb. Tegyük fel, hogy
elakadunk, azaz olyan
H
gráfot kapunk, melyben minden pont
foka legalább
1
−
1
k
+
ɛ
2
V
H
. Ekkor ha
N
=
V
H
elég nagy, az előző feladatból
következik az állítás. Tehát elég azt megmutatni, hogy
N
nem lehet túl kicsi (és hogy
egyáltalán elakadunk, azaz
N
≠
0
).
H
konstruálása során összesen legfeljebb
élt hagytunk el. A maradéknak legfeljebb
N
2
éle van, tehát
vagy ami ezzel ekvivalens,
Tehát ha
n
nagy, akkor
N
is, és az állítás következik.
(c) Legyen
χ
G
0
=
k
+
1
. Tekintsük a
H
n
,
k
Turán-gráfot, mint 10.34 megoldásában.
Ez
k
-kromatikus és emiatt nem tartalmaz
G
0
-t. Így
vagyis
Indirekte tegyük fel, hogy tetszőlegesen
nagy
G
gráfok vannak, melyek nem tartalmazzák
G
0
egy példányát, és melyekre
Ekkor (b) szerint egy megfelelően nagy
G
tartalmazna
k
+
1
olyan diszjunkt
V
G
0
méretű halmazt, melyekre bármely két
különböző ilyen halmazba tartozó pont szomszédos. De
ekkor
G
0
már eleve részgráfja ezen
részgráfoknak, ami ellentmondás.
[P. Erdős–A. H. Stone,
Bull. Amer. Math. Soc. 52 (1946),
1089–1091. Ez a bizonyítás P. Erdős
–M. Simonovits, Studia Sci. Math. Hung.
1 (1966) 51–57. egy specializációja.]
- 39. feladat F Ö
Legyen
n
0
=
V
G
0
. Először az ötlettárban
megfogalmazott állítást bizonyítjuk,
pontosabban:
(
∗
) Ha
G
≠
H
n
,
k
egy
n
≥
N
k
,
n
0
pontú és
E
H
n
,
k
élű egyszerű gráf és
G
nem tartalmaz
G
0
-t, akkor tartalmaz egy
n
1
=
n
−
2
k
n
0
pontú
G
1
feszített részgráfot, melyre
Valójában
N
=
N
k
,
n
0
-t úgy választjuk, hogy egy
n
≥
N
pontú és
E
H
n
,
k
élű gráf tartalmazzon
k
diszjunkt
A
1
,
…
,
A
k
olyan halmazt, melyekre
A
i
=
2
n
0
és bármely két különböző
A
i
halmazba tartozó pont szomszédos.
Ilyen
N
10.38b szerint létezik, mivel
Mármost minden
x
∉
A
1
∪
…
∪
A
k
-ra kell, hogy legyen legalább
2
n
0
A
1
∪
…
∪
A
k
-beli pont, mely nem szomszédos
x
-szel. Ellenkező esetben
x
minden halmaz legalább egy pontjával,
és egy kivételével minden halmaz legalább
n
0
pontjával szomszédos lenne. Így
választhatnánk egy olyan
B
i
⊆
A
i
,
B
i
=
n
0
halmazt, melyre
x
szomszédos mondjuk
B
1
∪
…
∪
B
k
−
1
minden pontjával, és legalább egy
B
k
-beli ponttal. Mivel
G
0
−
e
k
-kromatikus, a
B
1
∪
…
∪
B
k
∪
{
x
}
által feszített részgráf tartalmazza
G
0
-t, ami ellentmondás.
Vegyük észre azt is, hogy egyenlőség csak akkor
állhat fenn, ha
x
egy kivételével minden
A
i
minden pontjával, de ezen egy
A
i
egyetlen pontjával sem szomszédos.
Tegyük fel, hogy az egyenlőség minden
x
-re fennáll. Ekkor az
x
-eket besorolhatjuk
k
osztályba,
C
1
,
…
,
C
k
-ba úgy, hogy
x
∈
C
i
szomszédos
A
j
,
j
≠
i
minden pontjával, de
A
i
egyetlen pontjával sem. Két azonos
C
i
-be tartozó pont nem lehet szomszédos,
hiszen ekkor a fenti módon találnánk
G
0
-t
G
-ben. Így
G
k
-kromatikus. A
k
-kromatikus gráfok közül természetesen
H
n
,
k
-nak van a legtöbb éle, ami ellentmond
G
≠
H
n
,
k
és
E
G
≥
E
H
n
,
k
-nak.
Tehát valamely
x
A
1
∪
…
∪
A
k
-nak
2
k
−
2
n
0
-nál kevesebb pontjával szomszédos.
Így
A
1
∪
…
∪
A
k
elhagyásával kevesebb mint
M
=
4
k
2
n
0
2
+
n
−
2
k
n
0
2
k
−
2
n
0
él szűnik meg.
H
n
,
k
minden osztályából
2
n
0
pont elhagyása pontosan
M
élt szüntet meg, és
H
n
1
,
k
-t eredményezi. Tehát
Ezzel (
∗
)-ot bizonyítottuk.
Indirekte tegyük fel, hogy van egy
n
≤
2
k
n
0
N
2
+
N
pontú, legalább
E
H
n
,
k
élű egyszerű
G
≠
H
n
,
k
gráf, mely nem tartalmaz
G
0
-t. Legyen
n
i
=
n
−
2
k
i
n
0
. Válasszunk olyan
G
⊇
G
1
⊇
G
2
…
feszített részgráfokat, melyekre
V
G
i
=
n
i
és
E
G
−
E
H
n
,
k
<
E
G
1
−
E
H
n
1
,
k
<
…
. Ekkor
Nézzük meg, hogy a
G
1
,
G
2
,
…
sorozatnak mikor van vége. Tegyük fel,
hogy ez a
t
-ik lépésben következik be. (
∗
) szerint találunk
G
t
+
1
-t, kivéve, ha
G
t
≅
H
n
t
,
k
, vagy
E
G
t
<
E
H
n
t
,
k
, vagy
V
G
t
<
N
. (5) azonnal kizárja az első két
lehetőséget. Viszont ha
akkor
és így
ami ellentmondás. [M. Simonovits,
Theory of Graphs (P. Erdős–G. Katona, szerk.)
Akadémiai Kiadó, Budapest, 1968, 270–319.]
- 40. feladat F Ö
(a) Legyenek
A
1
,
…
,
A
N
k
a teljes
k
-szögek és
B
1
,
…
,
B
N
k
−
1
a teljes
k
−
1
-szögek
G
-ben. Tartalmazza
A
i
-t
a
i
darab teljes
k
+
1
-szög, és tartalmazza
B
i
-t
b
i
darab teljes
k
-szög.
Legyen
x
olyan nem
A
i
-beli pont, mely
A
i
-vel együtt nem alkot teljes
k
+
1
-szöget. Ekkor
x
nem szomszédos valamely
y
∈
A
i
-vel. Legyenek
U
1
,
…
,
U
k
−
1
az
A
i
∪
{
x
}
{
x
,
y
}
-t tartalmazó
k
elemű részhalmazai. Ekkor bármely
A
i
,
U
j
pár egy teljes
k
pontú gráfból és egy nem teljes
k
pontú gráfból áll, és
A
i
∩
U
j
=
k
−
1
. Így
egy alsó korlát azon
A
,
U
párok számára, melyekben
A
egy teljes
k
pontú gráf,
U
egy nem teljes
k
pontú gráf és
A
∩
U
=
k
−
1
.
Másrészről az ilyen
A
,
U
párok száma nyilvánvalóan
Tehát azt kapjuk, hogy
Tudjuk, hogy
(6) bal oldala egyenlő a
kifejezéssel, míg a jobb oldal becsülhető a
Jensen-egyenlőtlenséggel:
Innen (a) adódik.
[J. W. Moon–L. Moser,
Mat. Kut. Int. Közl.
7 (1962),
283–286.]
(b) Az ötlettárban kimondott (
∗
) becslés (a)-ból egyszerű indukcióval
adódik. Ezután (
∗
)-ból következik, hogy
- 41. feladat F Ö
(a)
T
n
bármely ponthármasa vagy 3 hosszúságú
irányított kört, vagy tranzitív háromszöget alkot. Ha
két élnek közös kezdőpontja van, akkor pontjaik
tranzitív háromszöget alkotnak és minden tranzitív
háromszög tartalmaz ilyen élpárt. Így a tranzitív
háromszögek száma
(A Jensen-egyenlőtlenség miatt, mivel
∑
d
i
=
n
2
). Tehát a 3 hosszúságú irányított
körök száma legföljebb
(b) Legyen
x
∈
V
T
, és jelölje
X
és
Y
rendre azon
y
pontok halmazát, melyre
y
,
x
∈
E
G
, illetve
x
,
y
∈
E
G
. Kell, hogy legyen
X
-et
Y
-nal összekötő él, különben
T
nem lenne erősen összefüggő. Ez az él
x
-szel együtt 3 hosszúságú irányított
kört alkot.
n
szerinti indukcióval bebizonyítjuk,
hogy a 3 hosszúságú körök száma legalább
n
−
2
.
n
=
3
-ra ez nyilvánvaló.
6.13 szerint találunk olyan
x
pontot, melyre
T
−
x
erősen összefüggő; így az indukciós
feltétel miatt
T
−
x
legalább
n
−
3
3 hosszúságú irányított kört
tartalmaz. Mint azt fent megjegyeztük, legalább egy 3
hosszúságú irányított kör szomszédos
x
-szel; így
T
legalább
n
−
2
3 hosszúságú irányított kört
tartalmaz.
Megjegyzés: Mindkét állítás alapvetően éles: ha
n
páratlan, akkor 5.13 szerint
K
n
-nek van olyan irányítása, hogy minden
pont kifoka
n
−
1
2
és ezen turnement pontosan
1
4
n
+
1
3
darab 3 hosszúságú irányított kört
tartalmaz. Másrészről tekintsünk egy tranzitív
turnamentet és fordítsuk meg az „első” és „utolsó”
pontját összekötő
e
él irányítását. Ekkor olyan erősen
összefüggő turnamentet kapunk, melyben minden 3
hosszúságú irányított kör tartalmazza
e
-t, tehát ezek száma
n
−
2
.
- 42. feladat F Ö
Először
n
szerinti indukcióval megmutatjuk, hogy
minden
3
≤
k
≤
n
-hez minden
x
ponton keresztül létezik
k
hosszúságú irányított kör.
n
=
k
-ra az állítás igaz, mert
T
6.11 miatt tartalmaz Hamilton-kört.
Tegyük fel, hogy
k
<
n
.
6.13 szerint van olyan
y
≠
x
pont, melyre
T
−
y
erősen összefüggő. Tehát
T
−
y
tartalmaz egy
x
-en áthaladó
k
hosszúságú irányított kört, és így
T
is.
Most már úgy, mint az előző megoldás (b)
részében, könnyű indukcióval adódik, hogy
3
≤
k
≤
n
-ra
T
legalább
n
−
k
+
1
darab
k
hosszúságú irányított kört tartalmaz.
Így az irányított körök teljes száma
Az állítás éles arra a turnamentre, melyet a
tranzitívból a Hamilton út éleinek megfordításával
kapunk.
- 43. feladat F Ö
Azt már tudjuk, hogy Hamilton út létezik (lásd
5.20). Legyenek
e
1
,
…
,
e
n
2
független élek. Az a Hamilton út,
melynek a
2
i
−
1
-ik éle
e
i
i
=
1
,
…
,
n
2
, egyértelműen meg van határozva. Így
a Hamilton utak száma nem nagyobb annál,
ahányféleképpen
n
2
független élt ki tudunk választani (és
rendezni).
e
1
kiválasztására
n
2
lehetőségünk van;
e
2
-re
n
−
1
2
, stb. Így ahányféleképpen
kiválaszthatjuk
e
1
,
…
,
e
n
2
-t kiválaszthatjuk, az
- 44. feladat F Ö
(a) Feltehetjük, hogy
n
=
2
k
−
1
.
k
szerinti indukcióval bizonyítjuk, hogy
T
tartalmaz
k
pontú tranzitív részturnamentet.
k
=
1
-re az állítás triviális.
Tegyük fel, hogy
k
>
1
, és válasszunk egy
x
∈
V
T
-t. Legyen
X
és
Y
rendre azon
z
pontok halmaza, melyekre
z
,
x
∈
E
T
és
x
,
z
∈
E
T
. Mivel
X
+
Y
=
2
k
−
1
−
1
, feltehetjük, hogy pl.
X
≥
2
k
−
2
. Ekkor az indukciós feltétel szerint
X
egy
k
−
1
pontú
T
1
tranzitív részturnamentet feszít.
x
-szel együtt
T
1
egy
k
pontú tranzitív részturnamentet
ad.
(b) Az állítást
k
szerinti indukcióval bizonyítjuk.
k
=
1
-re az állítás ismét triviális. Tegyük
fel, hogy
k
>
1
. Definiáljuk
f
x
-et a következőképpen:
Ekkor
f
x
konvex függvény.
Legyen
V
T
=
{
x
1
,
…
,
x
n
}
és legyen
x
i
kifoka
d
i
. Az indukciós feltétel szerint
legalább
f
d
i
darab
k
−
1
pontú tranzitív turnamentet feszít az a
d
i
számú pont, melyekkel
x
i
össze van kötve; ez
f
d
i
k
pontú
x
i
forrású tranzitív turnamentet ad.
Tehát a
k
pontú tranzitív turnamentek száma
(és mivel
n
−
1
2
≥
2
k
−
1
−
1
),
ami bizonyítja az állítást.
(c) Ez alkalommal
n
-re alkalmazunk indukciót az ötlettár
állításának bizonyításához.
n
≤
k
-ra az állítás igaz. Legyen
n
>
k
. 6.13 szerint van olyan
x
pont, melyre
T
−
x
erősen összefüggő. Tehát legalább
n
−
3
k
−
2
3 olyan
k
-as van
T
−
x
-ben, mely tartalmaz 3 hosszúságú
irányított kört. 10.40 megoldásából azt kapjuk, hogy
van
x
-en áthaladó 3 hosszúságú irányított
kör és van további
n
−
3
k
−
3
k
-as, mely ezt a háromszöget
tartalmazza. Ebből
3 hosszúságú irányított kört tartalmazó
k
-as adódik, mint azt
állítottuk.
Mivel egy
k
pontú tranzitív turnament nem
tartalmaz irányított háromszöget, ezek száma
Figyeljük meg, a 10.41 megoldásában szereplő
turnamentre egyenlőség áll.