- 1. feladat F Ö
(a) A gráf fokszámait összeadva minden élt
kétszer veszünk számításba (mindkét végpontjánál
egyszer). Így a fokszámok összege az élek számának
kétszerese.
Mivel
3
+
3
+
3
+
3
+
5
+
6
+
6
+
6
+
6
+
6
+
6
páratlan (páratlan számú páratlan tag
van az összegben), ez a sorozat nem lehet semmilyen
gráf fokszámsorozata. Ez általánosan azt adja, hogy a
páratlan fokszámok száma páros.
(b) Legyenek
d
1
,
…
,
d
k
a „felső” pontok fokszámai,
r
1
,
…
,
r
e
az „alsó” pontok fokszámai egy páros
gráfban. Ekkor mind
d
1
+
…
+
d
k
, mind
r
1
+
…
+
r
e
az élek számát adja meg, így
Tegyük fel, hogy a fokszámok a feladatban
megadottak. Legyen mondjuk
d
1
=
5
. Ekkor (1) jobb oldala osztható
3-mal, míg a bal oldala nem. Így a sorozat nem lehet
páros gráf fokszám-sorozata (bár általános gráfé
igen).
(c) Mivel a 9 fokú pont minden más ponttal
szomszédos, ezért mindkét elsőfokú ponttal is
szomszédosnak kell lennie. Így a 8 fokú pont nem lehet
ezek egyikének sem szomszédja; de akkor csak 7 pont
marad, tehát nem lehet 8 fokú pont [vö. 7.51.
feladat].
- 2. feladat F Ö
Tegyük fel, hogy létezik
k
-reguláris egyszerű
n
pontú gráf. 5.1a megoldásából
k
⋅
n
az élek számának kétszerese, így
az is triviális, hogy
Megmutatjuk, hogy ha (2) és (3) teljesül,
akkor létezik
k
-reguláris egyszerű
n
pontú gráf.
1. eset:
k
páros. Tekintsük egy reguláris
n
-szög pontjait és kössük össze
mindegyiket az 1 szomszédaival, a
2
szomszédaival, stb., a
(
k
∕
2
)
-adik szomszédaival. Mivel
k
<
n
, nem lesznek többszörös élek.
(29. ábra).
2. eset:
k
páratlan. Ekkor (2) miatt
n
páros. Tekintsük az 1. esetben
konstruált
n
pontú,
k
−
1
fokszámú gráfot. (3) miatt a
leghosszabb átló végpontjai nincsenek összekötve; így
ha ezeket az éleket is behúzzuk,
k
-reguláris egyszerű gráfot
kapunk.
- 3. feladat F Ö
Ha a
G
gráf páros és
C
a
G
egy köre, akkor
C
a
G
részgráfjaként szintén páros gráf,
tehát páros hosszúságú is. Tegyük fel, hogy
G
-nek csak páros köre van, és legyen
P
1
és
P
2
két
(
x
,
y
)
-utak.
|
V
(
P
1
)
|
szerinti indukcióval bizonyítjuk, hogy
P
1
és
P
2
azonos paritású. Ha
P
1
∪
P
2
kör, akkor amiatt, hogy ez a kör
páros,
P
1
és
P
2
azonos paritású.
Így tegyük fel, hogy
P
1
-nek és
P
2
-nek van egy közös pontja,
z
. Ossza őket
z
rendre
P
1
′
,
P
1
″
és
P
2
′
,
P
2
″
részekre. A jelölés választható úgy,
hogy
P
1
′
és
P
2
′
(
x
,
z
)
-utak legyenek és így az indukciós
feltétel miatt azonos paritásúak. Hasonlóan
P
1
″
és
P
2
″
is azonos paritású, ami bizonyítja,
hogy
P
1
=
P
1
′
∪
P
1
″
és
P
2
=
P
2
′
∪
P
2
″
szintén.
A 2-színezhetőség bizonyításához feltehetjük,
hogy
G
összefüggő. Jelölje
π
(
x
,
y
)
az
(
x
,
y
)
-utak közös paritását (
π
(
x
,
y
)
=
0
vagy 1). Legyen
x
0
∈
V
(
G
)
és
Ekkor
{
S
0
,
S
1
}
jó 2-színezés; hiszen legyen
(
u
,
v
)
egy él és
u
∈
S
0
(mondjuk), és tekintsünk egy
(
x
0
,
u
)
utat,
P
-t. Ha
v
∉
V
(
P
)
, akkor
P
+
(
u
,
v
)
egy
(
x
0
,
v
)
út, így
Ha
v
rajta van
P
-n és azt
(
x
0
,
v
)
és
(
v
,
u
)
, rendre a
P
1
és
P
2
darabokra osztja, akkor
P
2
+
(
u
,
v
)
kör, és így páros. Ez azt jelenti, hogy
P
2
hossza páratlan. Mármost
Ez mutatja, hogy
π
(
x
0
,
v
)
=
1
, azaz
v
∈
S
1
.
Irányított gráfokra nem igaz az állítás, hiszen
például a tranzitív irányítású háromszög nem páros és
páratlan hosszúságú köre sincs (hiszen irányított kört
nem tartalmaz).
Ellenben igaz marad az állítás erősen összefüggő
irányított gráfokra. Ennek bizonyításához először azt
mutatjuk meg, hogy ha
G
-ben nincs páratlan hosszúságú
irányított kör és
P
egy
(
x
y
)
út, míg
Q
egy
(
y
,
x
)
út, akkor
P
és
Q
azonos paritású. Ez a fenti bizonyítás
első feléhez teljesen hasonlóan látható be. Legyen
P
1
és
P
2
két
(
x
,
y
)
út, és válasszunk egy
Q
(
y
,
x
)
-utat (itt használjuk a feltételt,
hogy
G
erősen összefüggő), ekkor
P
1
és
Q
azonos paritású. De azonos paritású
P
2
és
Q
is, emiatt
P
1
és
P
2
úgyszintén. Ez után a bizonyítás az
irányítatlan esettel azonos módon fejezhető be.
- 4. feladat F Ö
Ha van egy megfelelő
p
(
x
)
potenciál, akkor bármely sétán a
szükséges munka a végpontok potenciálja közti változás.
Ez speciálisan bármely zárt sétára 0, így bármely körön
is az.
Tegyük fel, hogy bármely körön a szükséges
összmunka 0. Azt állítjuk, hogy bármely
W
zárt sétára is 0. Indukciót
alkalmazunk
W
hosszára. Ha
W
kör, akkor az állítás maga a feltétel.
Így tegyük fel, hogy
W
egy
x
pontot kétszer érint.
x
két kisebb zárt sétára osztja
W
-t,
W
1
-re és
W
2
-re.
W
1
és
W
2
mentén az összmunka az indukciós
feltétel miatt 0, de ekkor
W
mentén is 0.
Ha
P
1
és
P
2
tetszőleges
(
x
,
y
)
séták, akkor alkothatunk egy
W
zárt sétát
P
1
-en
x
-ből
y
-ba haladva, majd
P
2
-n vissza. Mivel
W
mentén az összmunka 0, így
P
1
és
P
2
azonos munkát igényel.
Rögzítsünk egy
x
0
pontot és definiáljuk
p
(
y
)
-t az
x
0
-tól
y
-ig szükséges munkával. A fentiek
miatt ez független a választott
(
x
0
,
y
)
úttól. Könnyű látni, hogy ez a
potenciál-függvény eleget tesz a
követelményeknek.
Megjegyezzük, hogy a
v
(
e
)
és
p
(
x
)
értékei tetszőleges csoportból
származhatnak. Továbbá ha ebben a csoportban minden
elem rendje 2, akkor
G
irányításának nincsen szerepe.
- 5. feladat F Ö
Először legyen
C
páros irányított kör.
C
2-színezhető úgy, hogy minden pontja
ellentétes színű ponthoz csatlakozik, egyszerűen a
pontok váltakozó színezésével. Ha
C
nem feszíti
G
-t, a következőképpen terjesztjük ki
ezt a színezést. Van egy
C
-hez kapcsolódó
x
1
pont, mert
G
erősen összefüggő; hasonlóan válasszuk
az
x
2
,
…
,
x
m
pontokat úgy, hogy
x
i
C
∪
{
x
1
,
…
,
x
i
−
1
}
-hez van kapcsolva (
i
=
2
,
…
,
m
). Végül
G
minden nem
C
-n lévő pontja az
x
i
-k közé fog tartozni. Ha
C
∪
{
x
1
,
…
,
x
i
−
1
}
már ki van színezve 2 színnel, adjuk
x
i
-nek az azzal ellentétes színt, mint
ami azé a ponté, melyen keresztül
x
i
a
C
∪
{
x
1
,
…
,
x
i
−
1
}
-hez kapcsolódik. Nyilvánvaló, hogy ez
a színezés rendelkezik a kívánt tulajdonsággal.
Tegyük fel, hogy
G
-nek van a szóban forgó tulajdonságú
2-színezése, melynek szín-osztályai
S
1
és
S
2
. Jelölje
G
0
azt a gráfot, mely az
S
1
és
S
2
közötti élekből áll. Mivel
G
0
-nak a feltétel szerint minden kifoka
pozitív, tartalmaz egy
C
irányított kört. Tekintve, hogy
G
0
páros,
C
páros hosszúságú kör.
- 6. feladat F Ö
Legyen
L
egy maximális
G
-beli zárt vonal. Ha
L
nem tartalmazza az összes élt, akkor
van olyan
e
(
x
,
y
)
él, melynek van egy közös pontja
L
-lel; hiszen különben
L
a
G
egy összefüggő komponense lenne, ami
lehetetlen, mert
G
gyengén összefüggő. Feltehetjük, hogy
e
az
L
-en lévő
x
pontban kezdődik.
Induljunk ezen az élen, és sétáljunk végig
G
−
E
(
L
)
élein, minden élt csak egyszer
használva, amíg ez lehetséges. Nem akadhatunk el
egyetlen
z
≠
x
pontban sem; hiszen ugyanannyi él
hagyja el
G
−
E
(
L
)
-t, mint amennyi érkezik bele, és
akárhányszor egy
z
-t elhagyó élt használunk, előtte
kellett használnunk egy ide érkezőt is.
Tehát
x
-ben akadunk el; most térjünk át
L
-re
x
-ből indulva. Így végül is egy
L
-nél hosszabb vonalat kaptunk.
- 7. feladat F Ö
(a) Bármely pont kifoka és befoka egyaránt
n
-nel egyenlő, és
G
erősen összefüggő, mert
(
a
1
,
…
,
a
k
)
,
(
a
2
,
…
,
a
k
,
b
1
)
,
(
a
3
,
…
,
b
2
)
, …,
(
a
k
,
b
1
,
…
,
b
k
−
1
)
,
(
b
1
,
…
,
b
k
)
egy
(
a
1
,
…
,
a
k
)
-ból
(
b
1
,
…
,
b
k
)
-ba vezető irányított séta. Tehát
G
Euler-gráf.
(b) A
k
=
2
eset triviális. Legyen
k
≥
3
. Ha
(
a
,
b
)
a
G
k
−
1
,
n
egy éle, akkor definíció szerint
a
=
(
x
1
,
…
,
x
k
−
1
)
és
b
=
(
x
2
,
…
,
x
k
)
valamely
1
≤
x
i
≤
n
-re. Azonosítsuk
G
k
,
n
(
x
1
,
…
,
x
k
)
pontját az
(
a
,
b
)
éllel. Azonnal adódik, hogy ez egy
izomorfizmust ad
L
(
G
k
−
1
,
n
)
és
G
k
,
n
között.
G
k
−
1
,
n
egy Euler-vonala
L
(
G
k
−
1
,
n
)
egy Hamilton-körét adja.
- 8. feladat F Ö
Legyen
(
a
1
,
…
,
a
2
k
)
a
G
k
,
2
egy irányított Hamilton-köre. Ekkor a
szomszédosság definíciója szerint
a
1
=
(
x
1
,
…
,
x
k
)
,
a
2
=
(
x
2
,
…
,
x
k
,
x
k
+
1
)
, …,
a
2
k
=
(
x
2
k
,
x
1
,
…
,
x
k
−
1
)
. Azonosítsuk az
x
1
,
…
,
x
2
k
számokat az irányított kör pontjaival.
Ekkor a
k
hosszúságú ívek az
a
1
,
…
,
a
2
k
0
-
1
-sorozatokat adják. Mivel egy
Hamilton-kör minden pontot pontosan egyszer tartalmaz,
az ívek minden 01-sorozatot pontosan egyszer
adnak.
- 9. feladat F Ö
Ha az ötlettárban leírt
L
1
,
…
,
L
d
darabok adottak, bármely permutációjuk
egy Euler-vonalat határoz meg, és ezen Euler-vonalak
közül kettő akkor és csak akkor azonos, ha a két
permutácó ciklikus permutációként azonos. Tehát
L
1
,
…
,
L
d
-ből
(
d
−
1
)
!
darab Euler-vonal adódik. Ez
bizonyítja, hogy az Euler-vonalak teljes száma osztható
(
d
−
1
)
!
-sal, ami páros, hiszen
d
≥
3
.
- 10. feladat F Ö
Kizárólag
x
0
-ban akadhatunk el; ez ugyanúgy
adódik, mint 5.6-ban. Tegyük fel, hogy
G
-nek vannak olyan élei, melyek
nincsenek rajta az általunk bejárt
L
vonalon.
L
minden
x
0
-hoz kapcsolódó élt tartalmaz; ez
nyilvánvaló az
x
0
-t elhagyó élekre és adódik a belépő
élekre is
d
+
(
x
0
)
=
d
−
(
x
0
)
miatt. Ha
(
x
,
y
)
∉
L
, akkor
T
(egyetlen)
x
-ből induló éle sem
L
-beli (
∗
) miatt. Így
T
-nek vannak nem
L
-beli élei. Vegyünk egyet, melynek
z
végpontja legközelebb van
x
0
-hoz (
T
-n mérve a távolságot). Mivel
L
nem használja az összes
z
-be befutó élt,
z
-be
d
+
(
z
)
=
d
−
(
z
)
-nél kevesebbszer tér vissza, így (
∗
) miatt nem használja az (egyetlen)
T
-beli
z
-t elhagyó
(
z
,
u
)
élt. Ellenben
u
közelebb van
x
0
-hoz, mint
z
(
T
-n mérve), ami ellentmondás.
- 11. feladat F Ö
Minden Euler-vonalat úgy tekintünk, hogy az
x
0
pontból az
e
0
élen indul. Legyen
L
egy Euler-vonal, és
T
azon
(
x
,
y
)
(
x
≠
x
0
) élek halmaza, melyekre fennáll,
hogy
(
∗
) minden
x
-ből induló élt korábban használunk,
mint
(
x
,
y
)
-t.
Ekkor
T
egy feszítő fenyő. Hiszen azt látjuk,
hogy pontosan egy
T
-beli él indul minden
x
≠
x
0
pontból. Továbbá
T
irányított körmentes; hiszen ha
egy irányított kör
T
-ben, akkor
e
2
az utolsó
x
2
-höz csatlakozó él
L
-en, és így
e
1
megelőzi
e
2
-t. Hasonlóan
e
2
megelőzi
e
3
-t, …,
e
n
megelőzi
e
1
-t, ami ellentmondás.
T
definíciója biztosítja, hogy
L
előáll
T
-ből az előző feladat konstrukciója
szerint.
Ha
T
adott, akkor bármely belőle származó
Euler-vonalat karakterizálhatunk két rendezés
meghatározásával, melyeket
G
−
E
(
T
)
x
-ből,
x
≠
x
0
induló élein és
x
0
-ból induló,
e
0
-tól különböző, élein értelmezünk; a
rendezések mutatják, hogy az Euler-vonalnak milyen
sorrendben kell használnia az éleket. Tehát pontosan
(
d
0
−
1
)
!
…
(
d
n
−
1
−
1
)
!
ilyen Euler-vonal van. Így az
Euler-vonalak száma
(
d
0
−
1
)
!
…
(
d
n
−
1
−
1
)
!
×
(
x
0
gyökerű feszítő fenyők száma).
[Aardenne–Ehrenfest, de Bruijn].
- 12. feladat F Ö
Nem akadhatunk el
x
≠
x
0
-ban; ez ugyanúgy adódik, mint
5.6-ban. Állítjuk, hogy
x
0
„jó” pont. Ez azért igaz, mert ha van
olyan
(
x
0
,
y
)
, melyet nem használtunk
x
0
-tól
y
-ig, akkor nem akadtunk el; de ha
minden
(
x
0
,
y
)
élt használtunk már ebben az irányban,
akkor
x
0
-t
d
(
x
0
)
-szer hagytuk el, így
d
(
x
0
)
-szor kellett, hogy ide érkezzünk,
tehát minden
x
0
-ba vezető élt használtunk.
Tegyük fel, hogy találunk sétánk során egy
„rossz” pontot, és legyen
x
az első ilyen.
x
-be egy
(
y
,
x
)
élen érkezünk, és mivel most járunk
először
x
-ben, ez lesz a megjelölt él.
x
„rossz” volta azt jelenti, hogy
x
-be
d
(
x
)
-nél kevesebbszer érkeztünk és így (
∗
∗
) miatt nem használjuk
(
x
,
y
)
-t
x
elhagyására. Ez viszont
ellentmondásban van azzal az állítással, hogy
y
„jó”.
Emiatt minden pont, melyhez elérünk „jó” pont. A
„jó”-ság definíciója miatt a „jó” pontok szomszédait
elérjük a séta során, és így azok szintén „jó” pontok.
Így a jó pontok
G
egy összefüggő komponensét alkotják.
Mivel
G
összefüggő, minden pont „jó”. Ezzel
befejeztük a bizonyítást. [Tarry algoritmus].
- 13. feladat F Ö
Az ötlettárban szereplő állítás bizonyításához
legyen
C
1
a
G
egy köre (
G
nem erdő, mivel a legalább egy élű
erdőben van elsőfokú pont). Legyen
G
1
a
G
−
E
(
C
1
)
-beli izolált pontok elhagyásával
kapott gráf. Ekkor
G
1
páros fokszámú (minden fokszámot 2-vel
vagy 0-val csökkentettünk), tehát
az indukciós feltétel szerint, és így
Tegyük fel, hogy
G
páros fokszámú gráf. Ekkor
(izolált pontoktól eltekinthetünk). Minden
C
i
-t ciklikusan irányítva
G
egy kívánt irányítását kapjuk.
- 14. feladat F Ö
(a) Ha
G
-ben van Euler-vonal, akkor
természetesen összefüggő és páros fokszámú; és
megfordítva: ha összefüggő és páros fokszámú, akkor
5.13. szerint lehet úgy irányítani, hogy minden pont
kifoka és befoka egyenlő. Az eredményül kapott gráfban
5.6. miatt van Euler-vonal. Ez az Euler-vonal egyben
G
egy Euler-vonala is.
(b) Ha
G
′
az a gráf, melyet úgy kapunk, hogy
felveszünk egy új pontot és összekötjük
G
páratlan fokszámú pontjaival, akkor
G
′
páros fokszámú és összefüggő, tehát
van benne Euler-vonal. Az új pontot elhagyva ez a vonal
k
él-diszjunkt élsorozatra esik szét,
melyek lefedik
G
-t.
- 15. feladat F Ö
Feltehetjük, hogy
G
minden pontjának foka legalább
4.
Legyen
x
∈
V
(
G
)
és legyenek
A
1
,
…
,
A
2
d
az
x
-hez csatlakozó élek rövid kezdő
szakaszai, ebben ciklikus sorrendben. Azt is
feltehetjük, hogy ha
G
−
{
A
1
∪
…
∪
A
2
d
)
nem összefüggő (ez például akkor
lehetséges, ha
x
-hez hurokél illeszkedik), ekkor
A
1
és
A
2
különböző komponensbe kerülnek.
Távolítsuk el
A
1
∪
A
2
-t de kössük össze az
x
-től különböző végpontjukat egy új
A
ívvel (30. ábra). A kapott
G
′
síkgráf összefüggő: ez adódik abból az
észrevételből, hogy
G
−
(
A
1
∪
…
∪
A
2
d
)
minden komponense
x
-hez legalább két
A
i
-n keresztül kapcsolódik amiatt, hogy
G
Euler-gráf. Azt is észrevehetjük, hogy
G
′
-nek kevesebb éle van, mint
G
-nek. Így indukcióval
G
′
-ben van megfelelő Euler-vonal.
A
helyére ismét
A
1
∪
A
2
-t helyettesítve
G
egy megfelelő Euler-vonalát
kapjuk.
- 16. feladat F Ö
Az ötlettár állítása könnyen belátható. Rátérve a
feladat állításának bizonyítására, ez fa esetében
triviális (
2
(
n
−
1
)
−
n
+
1
=
1
, összhangban azzal a ténnyel, hogy
egy
G
fa egyetlen „jó” részgráfja
(
V
(
G
)
,
∅
)
).
Tegyük fel, hogy
G
összefüggő és
M
„jó” részgráfja van.
G
+
e
azon „jó” részgráfjai, melyek
e
-t nem tartalmazzák, azonosak
G
„jó” részgráfjaival, és így számuk
M
. Csak azt kell belátnunk, hogy az
e
-t tartalmazó „jó” részgráfok száma
ugyanez. Legyen
C
a
G
+
e
egy köre, mely tartalmazza
e
-t (ilyen van, mert
G
összefüggő). Ekkor
G
1
akkor és csak akkor lesz
G
+
e
egy
e
-t tartalmazó „jó” részgráfja, ha
(
V
(
G
)
,
E
(
G
1
)
△
E
(
C
)
)
egy
e
-t nem tartalmazó „jó” részgráf. Ez a
megfeleltetés kölcsönösen egyértelmű és bizonyítja az
állítást.
- 17. feladat F Ö
(a) Szorítkozhatunk egyszerű gráfokra, hiszen két
párhuzamos él elhagyása nem változtat az
állításon.
Ha minden pont foka páros, legyen
V
1
=
V
(
G
)
és
V
2
=
∅
. Tegyük fel, hogy
a
páratlan fokszámú pont. Legyen
S
a szomszédai halmaza. Definiáljuk
G
1
-et a következőképpen:
n
-re vonatkozó indukcióval feltehetjük,
hogy
V
(
G
1
)
=
W
1
∪
W
2
, ahol
W
1
és
W
2
a
G
1
páros fokszámú részgráfjait feszítik.
Mivel
feltehetjük, hogy
|
S
∩
W
1
|
páros és
|
S
∩
W
2
|
páratlan. Legyen
Ekkor
V
1
és
V
2
a
G
páros fokszámú részgráfjait feszítik.
Először legyen
x
∈
V
1
. Ha
x
∉
S
, akkor a
G
[
V
1
]
-beli foka nyilvánvalóan páros. Legyen
x
∈
S
. Ekkor
és itt minden tag páros. Hasonlóan adódik minden
x
∈
V
2
-re, hogy a foka
G
[
V
2
]
-ben páros.
(b) Legyen
v
egy új pont, melyet
V
(
G
)
minden pontjával összekötöttünk, és
legyen
G
1
az így kapott gráf. Az előző feladat
szerint
V
(
G
1
)
=
U
1
∪
U
2
, ahol
U
1
és
U
2
páros fokszámú részgráfot feszítenek.
Ha mondjuk
v
∈
U
2
, akkor
V
1
=
U
1
,
V
2
=
U
2
−
{
v
}
lesz
V
(
G
)
kívánt partíciója. [T. Gallai,
W. K. Chen, SIAM J. Appl. Math.
20
(1971), 526–529; a fenti bizonyítás Pósa Lajostól
származik].
(c)
V
(
G
)
egy olyan
S
részhalmazát keressük, melyben minden
v
∈
S
páros számú, minden
v
∈
V
(
G
)
∖
S
pedig páratlan számú
S
-beli ponttal van összekötve. Vegyünk
fel egy új
u
pontot
G
-ben és kössük össze minden páros fokú
ponttal. Alkalmazzuk (a)-t az így kapott
G
′
gráfra, hogy egy olyan
V
1
∪
V
2
=
V
(
G
)
∪
{
u
}
partíciót kapjunk, melyre
G
′
[
V
i
]
páros fokú. Feltehetjük, hogy
u
∈
V
2
; ekkor
S
=
V
1
eleget tesz a fenti
követelményeknek.
- 18. feladat F Ö
(a) Legyen
S
a
V
(
G
)
feletti teljes gráf
r
-elemű párosításainak halmaza.
Legyenek
e
1
,
…
,
e
m
a
G
¯
élei és
A
i
az
S
azon elemeinek halmaza, melyek
e
i
-t tartalmazzák. Feladatunk
meghatározása. A szita-formula
alkalmazásával (2.2 feladat)
Itt
|
A
i
1
∩
…
∩
A
i
ν
|
az
S
azon elemeinek száma, melyek
e
1
i
,
…
,
e
i
ν
-t tartalmazzák. Ez csak akkor nem
üres, ha
e
1
i
,
…
,
e
i
ν
függetlenek, és ekkor ez a szám
n
−
2
ν
2
r
−
2
ν
(
2
r
−
2
ν
−
1
)
!
!
. Így
(b) Legyen
n
=
2
k
. (a)-ból
tehát
(c) Legyen
A
a
G
csúcsmátrixa és tekintsük
det
A
-t. Itt a kifejezés minden főátlóra
szimmetrikus nem-zérus tagja megfelel egy 1-faktornak
és megfordítva. A kifejezés többi tagja páronként
megfeleltethető egymásnak a főátlóra való tükrözéssel.
Így
G
1-faktorainak száma és
det
A
azonos paritású, és akkor és csak
akkor páros, ha
det
A
eltűnik
G
F
(
2
)
fölött. Ez akkor van, ha
A
sorai
G
F
(
2
)
fölött lineárisan összefüggők, azaz
léteznek olyan
G
F
(
2
)
-beli nem csupa nulla
g
1
,
…
,
g
n
elemek, hogy
A
sorait rendre
g
1
,
…
,
g
n
-nel szorozva a sorok összege 0 lesz.
Legyen
S
azon pontok halmaza, melyekhez tartozó
g
i
1, ekkor
S
rendelkezik azon tulajdonsággal, hogy
minden pont páros számú elemével szomszédos.
Megfordítva: minden ilyen
S
halmaz megfelelő
g
1
,
…
,
g
n
együtthatókat szolgáltat.
[G. H. C. Little, Discrete Math.
2
(1972), 179–181.]
- 19. feladat F Ö
Legyen
S
a
V
(
G
)
fölötti teljes irányított gráf összes
Hamilton-útjának halmaza és legyenek
e
1
,
…
,
e
m
a
G
¯
élei. Jelölje
A
i
az
S
azon elemeinek halmazát, melyek
tartalmazzák
e
i
-t, ekkor
(a
ν
=
0
-hoz tartozó tag
|
S
|
). Itt
|
A
i
1
∩
…
∩
A
i
ν
|
az
e
i
1
,
…
,
e
i
ν
-t tartalmazó teljes irányított gráf
Hamilton-útjainak száma. Ez 0, hacsak
e
i
1
,
…
,
e
i
ν
nem alkotnak diszjunkt utakat; ez
utóbbi esetben
(
n
−
ν
)
!
, hiszen a
(
V
(
G
)
;
{
e
i
1
,
…
,
e
i
ν
}
)
gráfnak
n
−
ν
komponense van és minden
e
i
1
,
…
,
e
i
ν
-n átmenő Hamilton-út a komponensek
egy rendezését határozza meg és viszont. Emiatt
Ez bizonyítja, hogy
H
(
G
)
≡
H
(
G
¯
)
(
mod
2
)
.
Ha
G
irányítatlan gráf, akkor
S
-et,
e
i
-t és
A
i
-t hasonlóan definiálva
(4)-gyel azonos
formulát kapunk, de most
ha
e
i
1
,
…
,
e
i
ν
μ
megfelelő pont-diszjunkt utat
alkotnak. Ha
n
≥
4
, akkor ez páros is, kivéve, ha
ν
=
n
−
1
és
e
i
1
,
…
,
e
i
ν
Hamilton-utat alkotnak. Tehát a
fentihez hasonló következtetést vonhatunk le. [Szele
T.].
- 20. feladat F Ö
Ha az ötlettár állítása igaz, a feladat állítása
könnyen belátható: élek megfordításával olyan tranzitív
turnamentet kapunk, melynek egy Hamilton-útja van.
Mivel a paritás azonos maradt, az eredeti turnamentben
páratlan számú Hamilton-út volt.
Így tehát elég azt megmutatni, hogy ha
T
egy turnament és
T
′
a belőle egy
e
él irányításának megfordításával
származtatott turnament, akkor
Legyen
G
1
és
G
2
az a két irányított gráf, melyet
T
-ből az
e
él eltávolításával, illetve a
fordított irányú
e
él hozzáadásával kapunk. Ekkor
egyszerű számítással kapjuk, hogy
Továbbá
G
¯
1
előáll
G
2
-ből egyszerűen minden él
irányításának megfordításával, amiből
Végül
5.19 miatt. Így
ami bizonyítja az állítást [Rédei L.].
- 21. feladat F Ö
Ha
F
1
és
F
2
a
G
diszjunkt 1-faktorai, akkor
E
(
G
)
−
F
1
−
F
2
1-faktor. Ha adott
E
(
G
)
egy partíciója három 1-faktorra, akkor
választhatjuk
F
1
-nek az
e
-t tartalmazó 1-faktort, a másik kettő
közül bármelyiket
F
2
-nek. Így azon
(
F
1
,
F
2
)
1-faktor-párok
m
száma, melyekre
F
1
∩
F
2
=
∅
,
e
∈
F
1
,
e
∉
F
2
kétszerese
E
(
G
)
1-faktorokra történő partíciói
számának. Tehát
m
páros. Tekintsük
F
1
∪
F
2
-t; ez
V
(
G
)
-t lefedő páros körökből áll.
Megfordítva ha
H
⊆
E
(
G
)
olyan
k
diszjunkt páros körből álló
V
(
G
)
-t lefedő rendszer élhalmaza, mely
tartalmazza
e
-t, akkor
H
pontosan
2
k
−
1
féle képpen bontható fel
H
=
F
1
∪
F
2
-re (
F
1
és
F
2
1-faktorok,
e
∈
F
1
,
e
∉
F
2
). Így tehát ha
m
k
jelöli a
V
(
G
)
-t lefedő
k
diszjunkt páros körből álló és
e
-t tartalmazó rendszerek számát, akkor
Vegyük észre, hogy itt
m
1
az
e
-n átmenő Hamilton-körök száma, ami
miatt
[C. A. B. Smith]
- 22. feladat F Ö
Az állítást
|
V
(
G
)
|
-re alkalmazott indukcióval
bizonyítjuk. Ha
|
V
(
G
)
|
=
4
, akkor triviális. Azt is feltehetjük,
hogy
G
összefüggő.
Ha van kétszeres él
G
-ben, akkor minden Hamilton-körnek a
kettő közül egyiket kell használnia, így a
Hamilton-körök párokban fordulnak elő és csak abban
különböznek, hogy a két párhuzamos él közül melyiket
használják. Tehát a Hamilton-körök teljes száma megint
csak páros.
Tehát tegyük fel, hogy
G
egyszerű. Legyen
(
x
,
y
)
,
(
x
,
u
1
)
,
(
x
,
u
2
)
,
(
y
,
v
1
)
,
(
y
,
v
2
)
∈
E
(
G
)
. (lásd 14. ábra). Hagyjuk el
x
-et és
y
-t és kössük össze
u
1
-t
v
1
-gyel,
u
2
-t
v
2
-vel, hogy
G
′
-t kapjuk; hasonlóan kössük össze
u
1
-t
v
2
-vel és
u
2
-t
v
1
-gyel hogy
G
″
-t kapjuk.
G
Hamilton-körei vagy tartalmazzák, vagy
nem
(
x
,
y
)
-t.
(
x
,
y
)
-on keresztül négyféle Hamilton-kör
van, ezek rendre
(
u
1
x
y
v
1
)
-et,
(
u
1
x
y
v
2
)
-t,
(
u
2
x
y
v
1
)
-et,
(
u
2
x
y
v
2
)
-t tartalmazzák. (31. ábra). A számuk
legyen rendre
h
1
,
h
2
,
h
3
,
h
4
. Az
(
x
,
y
)
-t nem tartalmazó Hamilton-körök
(
…
u
1
x
u
2
…
v
1
y
v
2
…
)
vagy
(
…
u
1
x
u
2
…
v
2
y
v
1
…
)
sorrendben haladhatnak. Az ilyen
Hamilton-körök száma legyen
h
5
és
h
6
.
A fent definiált
h
1
darab Hamilton-kör kölcsönösen
egyértelműen megfeleltethető
G
′
azon Hamilton-köreinek, melyek
(
u
1
,
v
1
)
-et tartalmazzák, de
(
u
2
,
v
2
)
-t nem. Hasonlóan
h
2
,
h
3
és
h
4
a
G
″
és
G
′
azon Hamilton-köreinek számával
egyeznek meg, melyek tartalmazzák
(
u
1
,
v
2
)
-t,
(
u
2
,
v
1
)
-et, illetve
(
u
2
,
v
2
)
-t, de a másik új élt nem. A
G
gráf
h
5
darab Hamilton-köre
G
′
azon Hamilton-köreinek felel meg,
melyek mind
(
u
1
,
v
1
)
-et, mind
(
u
2
,
v
2
)
-t tartalmazzák és rajtuk
(
…
u
1
v
1
…
u
2
v
2
…
)
sorrendben haladnak végig. Hasonlóan a
h
6
darab Hamilton-kör
G
″
azon Hamilton-köreinek feleltethető
meg, melyek
(
u
1
,
v
2
)
-n és
(
u
2
,
v
1
)
-en
(
…
u
1
v
2
…
u
2
v
1
…
)
sorrendben haladnak át.
A
G
′
eddig számításba nem vett
Hamilton-körei azok, melyek
(
u
1
,
v
1
)
-en és
(
u
2
,
v
2
)
-n
(
…
u
1
v
1
…
v
2
u
2
…
)
sorrendben haladnak át, valamint azok,
melyek az új éleket nem tartalmazzák. Legyen
h
7
és
h
8
az ilyen Hamilton-körök száma.
G
″
-ben nem vettük még számításba a
(
…
u
1
v
2
…
v
1
u
2
…
)
formájú Hamilton-köröket, valamint
azokat, melyek az új élek közül egyet sem tartalmaznak.
Az ilyen Hamilton-körök száma könnyen látható, hogy
megint csak rendre
h
7
és
h
8
(32. ábra).
A
G
Hamilton-köreinek száma
h
1
+
h
2
+
h
3
+
h
4
+
h
5
+
h
6
≡
(
h
1
+
h
4
+
h
5
+
h
7
+
h
8
)
+
(
h
2
+
h
3
+
h
6
+
h
7
+
h
8
)
≡
0
(
mod
2
)
, mivel itt a zárójelben rendre
G
′
és
G
″
Hamilton-köreinek száma szerepel.
[J. Bosák]
- 23. feladat F Ö
Az ötlettár állításának bizonyításához legyen
F
∗
a
V
(
G
∗
)
-on értelmezett azon gráf, melyet a
G
∗
F
élei által nem keresztezett élei
alkotnak.
F
∗
nem tartalmaz irányított kört, hiszen
akkor az
F
ezen körön belüli pontjai nem lennének
körön kívüli ponttal összekötve. Továbbá
F
∗
összefüggő, mert ha
F
∗
=
F
1
∪
F
2
,
F
1
∩
F
2
=
∅
, akkor legyen
U
a
G
azon lapjainak uniója, melyek
„fővárosa”
F
∗
-beli. Ekkor
U
nem a teljes sík (
F
2
egyetlen pontja sem tartozik bele) és
emiatt a határa,
B
nem üres.
B
az
F
bizonyos éleiből áll, mindegyiknek
U
egy lapja van az egyik oldalán, és nem
U
-beli lap a másik oldalán. Így nincsen
elsőfokú pont a határon, azaz
B
tartalmaz kört. Ez
ellentmondás.
Tehát
F
→
F
∗
a
G
és a
G
∗
feszítőfái közötti kölcsönösen
egyértelmű megfeleltetést ad. Ezzel bizonyítottuk a
feladat állítását.
Megjegyzés:
Érvelésünk során alkalmaztunk néhány
sík-topológiai tényt, mint pl. a Jordan Tétel (minden
egyszerű zárt görbe a síkot két részre osztja).
Minthogy célunk a példák kombinatorikai tartalmának
megvilágítása, ezen állításokat bizonyítás nélkül
elfogadtuk.
- 24. feladat F Ö
Tekintsük a
G
és az
F
∗
egy 5.23. szerinti
F
feszítőfáját. Ekkor
és az
F
∗
definíciója szerint
Így
- 25. feladat F Ö
Mivel minden lap határán legalább három [négy] él
van és minden él pontosan két lapot határol, az
Euler-formula szerint
vagy ezzel ekvivalens formában
- 26. feladat F Ö
Feltehetjük, hogy nincsenek hurokélek. Indukciót
alkalmazunk
|
E
(
G
)
|
-re.
Legyen
F
az
e
1
,
…
,
e
m
élek által határolt lap. Azt állítjuk,
hogy minden
x
pont ezek közül páros sokkal
érintkezik, hiszen ha
x
-ben
k
„sarok” tartozik
F
-hez, akkor ezen „sarkok” közül nem
lehet kettőnek közös
e
éle, mert ez az él elvágóél lenne
(lásd 33. ábra), és emiatt
G
−
e
egy komponense pontosan egy páratlan
fokú pontot tartalmazna. Így
x
az
F
határának
2
k
élével érintkezik.
Hagyjuk el az
e
1
.
…
,
e
m
éleket. A megmaradó
G
′
síkgráf páros fokú, tehát lapjai
2-színezhetők az indukciós feltevés szerint.
G
′
egyik lapja
F
-nek és szomszédainak az uniója, a
többi lapja pedig azonos
G
többi lapjával. A színeket megcserélve
G
F
-be eső lapjain, de megtartva mindenhol
máshol a
G
lapjainak egy 2-színezését
kapjuk.
- 27. feladat F Ö
(a) Először színezzük a lapokat 5.26-nak
megfelelően 2 színnel, mondjuk pirossal és kékkel.
Ezután irányítsunk minden élt úgy, hogy egy adott
e
éllel érintkező piros lap a bal
oldalán legyen. Ez az irányítás eleget tesz a
követelményeknek. (Ehhez a részhez nem szükséges, hogy
G
egyszerű legyen.)
(b) Feltehetjük, hogy
G
összefüggő; mivel Euler-gráf,
kétszeresen él-összefüggő. „Sarok” alatt olyan
rendezett élpárokat értünk, melyek egy lap határán
egymást követik, ha a határon úgy mentünk végig, hogy a
lap balra helyezkedett el.
Tekintsük
G
éleinek bármely 2-színezését. Egy
i
-élű lap legfeljebb
⌊
i
∕
2
⌋
piros-kék sarokkal érintkezik. Így ha
f
i
jelöli az
i
-élű lapok számát, akkor a piros-kék
sarkok száma legfeljebb
Legyen
G
-nek
n
pontja és
m
éle; ekkor az Euler-formulából
és nyilvánvalóan
Tehát a piros-kék sarkok száma legfeljebb
2
m
−
2
(
m
−
n
+
1
)
=
2
n
−
2
<
2
n
, és így kell, hogy legyen olyan pont,
mely legfeljebb egy piros-kék sarokkal érintkezik.
Ebből következik, hogy ennél a pontnál a piros élek (és
a kék élek is) egymást követik az élek ciklikus
sorrendjében. (Ebben a formában a feladat állítása
kiterjeszthető minden síkbarajzolható gráfra.)
- 28. feladat F Ö
(a) Tegyük fel, hogy létezik olyan páros fokú
síkgráf, melynek egy lap kivételével minden lapja
háromszög, a kimaradó lapja pedig ötszög. Színezzük a
lapokat 2 színnel (5.26), pirossal és kékkel, legyen az
ötszög mondjuk piros. Számoljuk meg az éleket. Minden
kék lapnak 3 éle van a határán, és így minden élt
pontosan egyszer vettünk számításba; tehát az élek
száma osztható 3-mal. Másrészről a piros lapokat
összesen
3
k
+
5
él határolja (
k
a piros háromszög lapok száma), ennek
ugyanazt kellene adni az élek számára, ez pedig
ellentmondás.
(b) Az ötlettár szerint konstruált
G
′
gráf minden pontja páros fokú, esetleg
z
kivételével, de ekkor 5.1a miatt
z
szintén páros fokszámú. Legyen
a
1
+
1
,
a
2
+
1
,
…
,
a
2
s
+
1
a
z
-vel érintkező lapok mérete ciklikus
sorrendben. Színezzük a lapokat 2 színnel (34. ábra).
Az
a
1
+
1
méretű lapot tartalmazó színnek
(
a
1
+
1
)
+
(
a
3
+
1
)
+
…
+
(
a
2
s
−
1
+
1
)
+
3
k
él van a határán, a másik színnek
(
a
2
+
1
)
+
…
+
(
a
2
s
+
1
)
+
3
N
él. Mindkét esetben
G
összes élének számát kapjuk. Így
Továbbá azt is tudjuk, hogy
∑
i
=
1
2
s
(
a
i
−
1
)
=
5
. Könnyű belátni, hogy az egyenletek
egyetlen megoldása
(vagy fordítva). Tehát az ötszögnek pontosan
két szomszédos pontja páratlan fokszámú. [Gallai
T.]
- 29. feladat F Ö
A három szín legyen piros, kék és zöld. Minden
háromszögnek, melynek pontjai különböző színt kapnak, 1
piros-kék éle van; minden más háromszögnek 0 vagy 2.
Továbbá minden piros-kék élt kétszer számoltunk, a két
szomszédos háromszögben. Így tehát az összeg páros,
azaz a 3 különböző színt tartalmazó háromszögek száma
páros.
Megjegyzés: Az állítás speciális esete Sperner
algebrai topológiai lemmájának, mely ekvivalens egy
n
-dimenziós sokaság triangulációjára
megfogalmazott hasonló állítással.
- 30. feladat F Ö
Vegyük az ötlettárban definiált színezést. Ha van
olyan lap, melynek
x
,
y
és
z
pontjai rendre piros, kék és zöld
színűek, és mondjuk
z
∈
V
1
, akkor
z
a
V
1
-beli
(
x
,
a
)
úttal együtt egy
V
1
-beli
(
z
,
a
)
utat ad, ami miatt
z
-t pirosra kellett volna
színeznünk.
Ha
V
1
-ben nincs
(
a
,
c
)
út és
V
2
-ben nincs
(
b
,
d
)
út, akkor
c
és
d
zöld színű. Így ha behúzzuk az
(
a
,
c
)
élt, akkor olyan hárömszögű síkgráfot
kapunk, melyben csak az
a
b
c
lap érintkezik mindhárom színnel. Ez
ellentmond az előző feladatnak.
- 31. feladat F Ö
(a) Igaz; sőt
A
akkor és csak akkor reguláris, ha
det
A
≠
0
, mely állítás bizonyítása bármely
területen érvényes megfontolásokra épül.
(b) Igaz; mivel
(c) Hamis; mert találunk olyan
u
≠
0
vektort, melyre
u
T
u
=
0
(pl. ha
F
=
G
F
(
2
)
,
u
=
e
1
+
e
2
vagy
F
a komplex tér és
u
=
(
1
,
i
)
T
), és ekkor az
módon definiált
A
transzformáció eleget tesz annak, hogy
A
≠
0
,
y
A
T
A
x
=
(
A
y
)
T
A
x
=
0
bármely
x
és
y
esetén, tehát
A
T
A
=
0
.
(d) Hamis; ha
u
T
u
=
0
,
u
≠
0
, akkor legyen
M
=
〈
u
〉
(az
u
által generált altér); ekkor
M
⊆
M
⊥
.
(e) Hamis; ez előző
M
-re azt kapjuk, hogy
〈
M
,
M
⊥
〉
=
M
⊥
≠
V
, mert pl. az
e
1
,
…
,
e
n
vektorok egyike biztosan nem
ortogonális
M
-re.
(f) Igaz; legyen
A
az ötlettárnak megfelelő. Ekkor
Így
ami mutatja, hogy
dim
M
⊥
=
n
−
k
.
(g) Igaz; mert legyen
u
∈
M
, ekkor
u
az
M
⊥
minden elemére ortogonális, azaz
u
∈
(
M
⊥
)
⊥
. Tehát
Másfelől
ami bizonyítja az állítást.
- 32. feladat F Ö
(a)
x
∈
〈
M
,
M
⊥
〉
⊥
akkor és csak akkor, ha
x
mind
M
-re, mind
M
⊥
-ra ortogonális, vagyis
x
∈
M
⊥
∩
(
M
⊥
)
⊥
=
M
∩
M
⊥
. Így
Legyen
u
∈
M
∩
M
⊥
. Ekkor
u
∈
M
és
u
∈
M
⊥
, tehát
u
T
u
=
0
. Ez azonban azt jelenti, hogy
u
-ban az 1-esek száma páros, ami
ekvivalens azzal, hogy
u
T
j
=
0
. Tehát
j
∈
(
M
∩
M
⊥
)
⊥
=
〈
M
,
M
⊥
〉
. [Gallai T.; W. K. Chen,
SIAM J. Appl. Math. 20 (1971),
526–529.]
(b) Az ötlettárban szereplő azonosság
nyilvánvaló, hiszen
v
T
A
v
-ben az
A
mátrixnak a főátlón kívüli elemeiből
származó tagok
G
F
(
2
)
fölött páronként kiejtik egymást, míg
a nem-nulla főátlóbeli elemek adaléka
v
i
2
=
v
i
.
Tegyük fel, hogy
a
nincs benne
A
oszlop-terében. Ekkor létezik egy
v
0-1 vektor, mely
A
minden oszlopára ortogonális, de
a
-ra nem (5.31(g) miatt). Emiatt
A
v
=
0
és így
v
T
A
v
=
0
. Az ötlettár azonossága miatt ebből
a
T
v
=
0
adódik, ami ellentmondás.
A
-t egy
G
=
(
V
,
E
)
gráf csúcsmátrixaként tekintve a
következőt kapjuk: ha adott
T
⊆
V
, akkor létezik olyan
S
⊆
V
halmaz, melyre minden
v
∈
V
esetén
Ha
T
-t a páratlan fokszámú, páros
fokszámú, majd az összes pontok halmazának választjuk,
akkor rendre 5.17 (a)-t, (b)-t majd (c)-t kapjuk. [N.
Alon]
- 33. feladat F Ö
(a) Megmutatjuk, hogy
U
G
a vágásokból tevődik össze. A vágások
egy alteret alkotnak; hiszen az
S
1
és
S
2
halmazok által meghatározott vágások
összege az
S
1
△
S
2
által meghatározott vágás. Minden
csillag vágás. Megfordítva, az
S
által meghatározott vágás az
S
pontjai által meghatározott csillagok
összege.
x
csillaga egy
A
halmaz éleire akkor és csak akkor
ortogonális, ha az
A
által meghatározott részgráf
x
-nél páros fokszámú. Így
W
G
a páros fokszámú részgráfok
élhalmazaiból áll. 5.13 megoldása miatt
W
G
-t a
G
körei generálják.
Ha minden kör páros hosszúságú, akkor
j
=
(
1
,
…
,
1
)
minden körre ortogonális, tehát
j
∈
(
U
G
⊥
)
⊥
=
U
G
. Ez (a) szerint azt mondja, hogy
G
páros gráf. Ebből már következik
5.3.
5.16 bizonyításához meg kell határoznunk
dim
W
G
-t. 5.21f szerint elég meghatároznunk
dim
U
G
-t. Legyen
A
1
,
…
,
A
n
az összes csillag. Mivel
azt kapjuk, hogy
U
G
=
〈
A
1
,
…
,
A
n
−
1
〉
. Megmutatjuk, hogy
A
1
,
…
,
A
n
−
1
lineárisan függetlenek. Bármely köztük
lévő lineáris összefüggés
formájú lenne, hiszen
G
F
(
2
)
fölött dolgozunk. De
A
i
1
+
…
+
A
i
k
a
V
(
G
)
egy nem üres valódi részhalmaza által
meghatározott vágás, ami nem üres, mivel
G
összefüggő.
Tehát
dim
U
G
=
n
−
1
és
dim
W
G
=
m
−
n
+
1
, amit bizonyítani akartunk. 5.17
azonnal adódik 5.32-ből.
(b) Az állítás nem összefüggő gráfokra triviális,
úgyhogy tegyük fel, hogy
G
összefüggő. A felosztások száma, tehát
az
a
+
b
=
j
,
a
∈
U
G
,
b
∈
W
G
megoldásainak száma magától értetődően
|
U
G
∩
W
G
|
. Ez egyenlő az
U
G
minden elemére ortogonális
u
∈
U
G
vektorok számával.
Legyen
A
G
a
G
pont-él incidencia mátrixa és
A
0
a belőle egy sor kihúzásával adódó
mátrix. Ekkor
A
0
T
rangja
U
G
. Azt is tudjuk, hogy
A
0
T
kölcsönösen egyértelmű. Így minket az
olyan
x
vektorok száma érdekel, melyekre
minden
y
esetén. De ez akkor és csak akkor igaz
minden
y
-ra, ha
A
0
A
0
T
x
=
0
. Ezen egyenletnek akkor és csak akkor
van egyértelmű megoldása, ha
det
A
0
A
0
T
≠
0
(
mod
2
)
. 4.9 szerint ez azt jelenti, hogy a
feszítő fák száma páratlan.
- 34. feladat F Ö
Legyenek
C
1
,
…
,
C
f
−
1
a véges lapok, melyeket
G
köreinek, és így
W
G
elemeinek tekintünk. Megmutatjuk, hogy
G
minden köre bizonyos
C
i
-k összege. Legyen
C
a
G
egy köre. Minden
C
i
lap
C
-n vagy kívül, vagy belül helyezkedik
el. Legyenek mondjuk
C
1
,
…
,
C
r
a
C
-n kívül eső lapok. Így
sőt ha
e
a
C
egy éle, akkor az
e
-vel érintkező két lap közül pontosan
egy esik
C
-n belülre, tehát
e
∈
E
(
C
1
+
…
+
C
r
)
. Ha
e
a
C
-n belül (kívül) helyezkedik el, akkor
ezen két lap közül mindkettő (egyik sem) található
C
-n belül, így
e
nem fordul elő
C
1
+
…
+
C
r
-ben. Másrészről ha
C
1
,
…
,
C
f
−
1
lineárisan összefüggők lennének,
mondjuk
akkor a
C
1
egy belső
x
pontjából rajzoljunk egy folytonos, a
pontokat elkerülő vonalat a végtelenbe. Ez a vonal a
C
1
,
…
,
C
r
lapok unióját egy olyan pontnál hagyja
el, mely a
G
egy
e
éléhez tartozik. Ekkor az
e
vel szomszédos két lap közül pontosan
egy tartozik
C
1
,
…
,
C
r
-be, tehát
ami ellentmondás.
Megjegyzés: Mivel
W
G
dimenziója az előző feladat szerint
m
−
n
+
1
, azt kapjuk, hogy
azaz megkapjuk az Euler formulát, legalábbis
kétszeresen összefüggő gráfokra. És megfordítva: az
Euler formula használata a bizonyítás egyik felét
feleslegessé tette volna.
- 35. feladat F Ö
(a) Legyen
e
∈
∑
i
∈
I
∪
J
C
i
, és mondjuk
e
∈
C
μ
,
μ
∈
I
∪
J
. Azt állítjuk, hogy
μ
∈
I
. Ez nyilván igaz, ha
μ
∉
J
. Tegyük fel, hogy
μ
∈
J
, ekkor mivel nincs más olyan
C
ν
,
ν
∈
I
∪
J
, mely
e
-t tartalmazza, ezért
ami miatt
μ
∈
I
. Tehát
e
∈
∑
i
∈
I
C
i
=
K
, vagyis
∑
i
∈
I
∪
J
C
i
⊆
K
. Mivel
K
egy kör és
∑
i
∈
I
∪
J
C
1
≠
∅
, azt kapjuk, hogy
Minthogy
K
egyértelműen felbontható a
C
i
-k összegére, így
(b) Ha
C
1
,
…
,
C
f
az összes kör, akkor könnyen látható,
hogy ezek pontosan a
G
tagjai (az elvágóéleket nem
számítva).
Legyen
K
≠
C
1
,
…
,
C
f
egy kör, melynek a
C
i
-k általi reprezentációja minimális
számú tagot tartalmaz. Legyen mondjuk
és pl.
C
1
∩
C
2
≠
∅
. Így
C
1
+
C
2
páros fokú, emiatt
ahol
K
1
,
…
,
K
s
él-diszjunkt körök. Közülük legalább
egy, mondjuk
K
1
, lineárisan független
C
1
,
…
,
C
f
-től, mert különben (5) azt mutatná,
hogy
C
1
,
…
,
C
f
lineárisan összefüggők. Legyen
(a)-ból
J
⊆
I
és így
I
minimalitását felhasználva kapjuk
J
=
I
-t. Tehát
K
=
K
1
és így
Azt állítjuk, hogy
K
=
C
1
+
C
2
. Tegyük fel, hogy van olyan
C
1
-beli él, mely nincsen benne mondjuk
K
∪
C
2
-ben. Ez az él egy
C
k
-hoz,
3
≤
k
≤
r
, tartozik. (6) igaz
C
k
-ra is, azaz
De (6) és
(7) azt adja, hogy
K
egy nem
C
1
-beli élének
C
2
-hez és
C
k
-hoz is tartoznia kell és így nem
fordulhat elő
∑
i
=
1
r
C
i
-ben, ami ellentmondás. Tehát
C
1
+
C
2
kör.
(c) indukciót alkalmazunk az élek számára. Legyen
mondjuk
C
1
+
C
2
=
C
kör. Hagyjuk el
C
1
és
C
2
közös éleit és az esetlegesen előálló
izolált pontokat. Legyen az így kapott gráf
G
′
.
Tekintsük a
C
,
C
3
,
…
,
C
f
rendszert. A konstrukcióból
nyilvánvaló, hogy
G
′
minden élét közülük legalább kettő
tartalmazza. Továbbá ha
A
a
G
′
egy páros fokszámú részgráfja, akkor
(
I
⊆
{
1
,
…
,
f
}
), és itt vagy
C
1
is és
C
2
is szerepel, vagy egyik sem. ami miatt
A
a
C
,
C
3
,
…
,
C
f
lineáris kombinációja. Továbbá
C
,
C
3
,
…
,
C
f
nyilvánvalóan lineárisan függetlenek.
Így az indukciós feltétel miatt
G
′
beágyazható a síkba úgy, hogy
C
,
C
3
,
…
,
C
f
lapok határai. Ahhoz, hogy megkapjuk
G
-t, vissza kell illesztenünk
C
1
∩
C
2
-t, ami egy
C
két pontját összekötő út, így ezt
megtehetjük és
C
1
,
C
2
új határok lesznek.
(d) Könnyen belátható, hogy egy gráf akkor és
csak akkor síkbarajzolható, ha minden tagja
síkbarajzolható. Egy hasonló állítás igaz arra a
tulajdonságra, hogy
W
G
-ben van olyan bázis, melynek minden
él legfeljebb két eleméhez tartozik. Így ezen két
tulajdonság ekvivalenciájának bizonyításához
szorítkozhatunk kétszeresen összefüggő gráfokra.
Ezekre a MacLane síkbarajzolhatósági feltétel
szükségessége 5.34-ből következik. Megjegyezzük, hogy
megkövetelhetjük, hogy a bázis elemei körök legyenek.
Hiszen tegyük fel, hogy létezik a
W
G
-nek olyan
A
1
,
…
,
A
f
bázisa, melyre minden él legfeljebb
kettőhöz tartozik.
A
1
él-diszjunkt körök uniója. Ezek
valamelyike nyilvánvalóan lineárisan független kell
A
2
,
…
,
A
n
-től.
A
1
-et ezzel a körrel helyettesítve
ugyanezzel a tulajdonsággal rendelkező bázist kapunk.
Hasonlóan folytatva helyettesíthetjük
A
2
,
…
,
A
f
-et körökkel.
A MacLane feltétel elégségessége (c)-ből
következik. [S. MacLane]
- 36. feladat F Ö
Tegyük fel, hogy
G
egy síkgráf és legyen
G
∗
a duális gráfja. Ekkor ha
ϕ
minden
e
∈
E
(
G
)
-hez a
G
∗
őt keresztező élét rendeli, akkor 5.23
miatt eleget tesz az állítás követelményeinek.
Megfordítva tegyük fel, hogy
G
∗
és
ϕ
létezik; megmutatjuk hogy ekkor
G
síkbarajzolható.
Először azt bizonyítjuk, hogy egy
G
∗
-beli csillag élei a
W
G
egy elemének feleltethetők meg. Hiszen
legyen
X
⊆
V
(
G
)
és tegyük fel, hogy
ϕ
(
X
)
egy
x
∈
V
(
G
∗
)
pont csillaga. Legyenek
B
1
,
…
,
B
s
a
G
∗
gráf
x
-hez illeszkedő ágai és legyen
A
i
az
(
x
,
B
i
)
élek halmaza. Ekkor
A
i
olyan nem szűkíthető halmaz, mely a
G
∗
minden feszítő fáját metszi. Emiatt
ϕ
−
1
(
A
i
)
olyan nem szűkíthető halmaz, melyet
G
∗
egyik feszítő fája sem tartalmaz, azaz
ϕ
−
1
(
A
i
)
kör. Így
Legyenek
C
1
,
…
,
C
n
∗
a
W
G
azon elemei, melyek
G
∗
-beli pontok csillagainak felelnek
meg. Ekkor triviálisan
G
minden élét a
C
i
-k közül pontosan kettő tartalmazza.
Továbbá ha
f
=
n
∗
−
1
, akkor
C
1
,
…
,
C
f
a
W
G
egy bázisát alkotja. Vagyis
(
G
∗
definíciója miatt), és
C
1
,
…
,
C
f
lineárisan függetlenek
G
F
(
2
)
fölött, mert
G
∗
megfelelő csillagai is azok.
Tehát
G
a MacLane feltétel miatt
síkbarajzolható. [H. Whitney]
- 37. feladat F Ö
(a)
G
triviálisan kétszeresen összefüggő. Az
indirekt feltevés legyen az, hogy
G
=
G
1
∪
G
2
V
(
G
1
)
∩
V
(
G
2
)
=
{
x
,
y
}
,
|
V
(
G
i
)
|
≥
3
mellett. Legyen
P
i
egy
(
x
,
y
)
út
G
i
-ben és
H
i
=
G
i
+
P
3
−
i
. Ekkor
H
i
síkbarajzolható; ágyazzuk a síkba
H
i
-t úgy, hogy a
P
3
−
i
a végtelen tartomány határán
helyezkedjen el (ez elérhető a sík egy megfelelő körére
vonatkozó invertálással). Ez után azonosítsuk az
x
és az
y
pontot és töröljük el a
P
i
utakat (35. ábra). Ezáltal
G
egy síkbaágyazásához jutunk, ami
ellentmondás.
(b) Legyen
(
x
0
,
…
,
x
m
)
egy
G
-beli leghosszabb út.
x
0
foka legalább 3, és nem szomszédos
ezen úton kívüli ponttal a maximalitás miatt. Így van
két szomszédja,
x
i
és
x
j
, melyekre
1
<
i
<
j
. Ekkor
(
x
0
,
…
,
x
j
)
egy kör húrral (vesd össze 6.35-tel
is).
(c) Legyen
(
x
,
y
)
a
C
kör egy húrja és válasszuk
C
-t úgy, hogy
G
−
(
x
,
y
)
-t a síkba ágyazva a
C
-n belüli lapok száma a lehető
legnagyobb legyen. Először is vegyük észre, hogy
nincsen
C
-n kívüli pont. Legyen ugyanis
G
0
a
G
−
V
(
G
)
egy komponense; indirekte tegyük fel,
hogy
G
0
a
C
-n kívülre esik. Mivel
G
3-szorosan összefüggő kell, hogy
legyen, a
C
-nek van 3 olyan
G
0
-lal szomszédos pontja, melyek közül
legalább kettő, mondjuk
u
és
v
nincsen
x
és
y
által elválasztva. Ekkor az
e
x
-et és
y
-t nem tartalmazó
(
u
,
v
)
ívet egy
G
0
-on keresztülmenő
(
u
,
v
)
-úttal helyettesítve egy
(
x
,
y
)
húrral és több belső lappal rendelkező
C
′
kört kapunk.
Ugyanezen okfejtéssel az is adódik, hogy
C
minden kívül futó húrja a
C
két
(
x
,
y
)
-ívének belső pontjait köti
össze.
Vizsgáljuk meg
C
azon hídjait, melyek
C
-n belüliek. Nevezzünk egy ilyen hidat
billenthetőnek, ha végpontjai nem választják el
C
egyetlen külső húrjának végpontjait
sem. Világos, hogy ezen hidakat mind „átbillenthetjük”
C
-n kívülre. A megmaradó hidak között
kell lenni olyannak, mely
C
mindkét
(
x
,
y
)
-ívéből tartalmaz belső pontot,
különben
x
-et és
y
-t
C
-n belül is összeköthetnénk és
G
síkbarajzolható lenne. Így van olyan
B
híd
C
-n belül és olyan
(
a
,
v
)
-húr
C
-n kívül, hogy a
B
végpontjai
C
-n elválasztják
a
-t
v
-től és
x
-et
y
-tól, és
{
a
,
v
}
és
{
x
,
y
}
szintén elválasztják egymást. Ez
többféleképpen lehetséges (36. ábra):
(a
∘
)
B
tartalmaz belső pontokat az
(
x
,
a
)
ívből és az
(
y
,
v
)
ívből (vagy szimmetrikusan
(
x
,
v
)
-ből és
(
y
,
a
)
-ból);
(b
∘
)
B
tartalmazza
v
-t, az
(
x
,
a
)
ív egy belső pontját és még az
(
y
,
a
)
ív egy
a
-tól különböző pontját (vagy hasonló
elrendezés);
(c
∘
)
B
tartalmazza
x
-et,
y
-t,
a
-t és
v
-t.
Vegyünk egy
P
utat, mely összeköti
B
két említett végpontját. A (b
∘
) esetben vegyünk egy utat, mely
P
-t összeköti egy harmadikkal. A (c
∘
) esetben vegyünk két utat, melyek
P
-t a másik két végponttal kötik össze.
Ha ez a két út találkozik, akkor legyen egy közös kezdő
szakaszuk. Így a (c
∘
) esetből két alesetet kapunk attól
függően, hogy az említett utak
B
-ben
H
vagy
X
formájúak-e (37. ábra).
Az (a
∘
) esetben
K
3
,
3
egy felosztását látjuk;
G
minimalitása miatt nem lehetnek más
élek vagy osztópontok, azaz
G
≅
K
3
,
3
. A (b
∘
) és a (c1
∘
) esetben a gráf valódi részként
tartalmazza
K
3
,
3
egy felosztását; ez lehetetlen, mivel
feltételünk szerint
G
minden valódi részgráfja
síkbarajzolható. A (c2
∘
) esetben látjuk
K
5
egy felosztását és így
G
≅
K
5
.
(d) Tegyük fel, hogy
G
síkbarajzolható. Ekkor
G
nyilvánvalóan nem tartalmazhatja
K
5
vagy
K
3
,
3
egy felosztását. Megfordítva: tegyük
fel, hogy
G
nem síkbarajzolható. Ekkor
G
tartalmaz egy minimális nem
síkbarajzolható
G
0
gráfot. Ha
G
0
-ból kivesszük a másodfokú pontokat
(elhagyva a pontot és a két szomszédját egymás után
kötve), egy újabb minimális nem síkbarajzolható gráfot
kapunk, ezúttal olyat, melyben minden pont foka
legalább 3. Ez a gráf (c) szerint vagy
K
5
, vagy
K
3
,
3
, tehát
G
0
a
K
5
vagy
K
3
,
3
egy felosztása.
[K. Kuratowski]
- 38. feladat F Ö
Indukciót alkalmazunk a pontok számára. Ha ez
legfeljebb 3, az állítás triviális.
Először azt mutatjuk meg, hogy ha
G
tetszőleges síkbarajzolható gráf,
akkor újabb élek behúzásával minden lapot háromszöggé
tehetünk anélkül, hogy párhuzamos éleket kapnánk.
Hiszen húzzunk be új éleket egészen addig, amíg nem
keletkeznek párhuzamos élek. A kapott
G
gráfban nincsen elvágópont; mert ha
G
=
G
1
∪
G
2
és
V
(
G
1
∩
G
2
)
=
{
x
}
, akkor vegyük a
G
i
−
x
egy
x
i
pontját annak a lapnak a határán, mely
mind
G
1
−
x
-szel, mind
G
2
−
x
-szel érintkezik;
x
1
és
x
2
egy további éllel összeköthető
lenne.
Tehát
G
kétszeresen összefüggő és emiatt
minden lap kör. Tegyük fel, hogy
C
egy legalább 4 pontú lap határa, és
legyen
a
,
b
,
c
és
d
négy egymást követő pont
C
-n. Az
(
a
,
c
)
és
(
b
,
d
)
élek valamelyikének hiányoznia kell;
hiszen mindkettőnek
C
-n kívül kellene futnia és így
keresztezniük kellene egymást. Tegyük fel, hogy
a
és
c
nem szomszédosak; ekkor egy
C
-n belül elhelyezkedő éllel
összeköthetők. Tehát
G
minden lapja háromszög.
Így elég az állítást háromszögelt síkgráfokra
bizonyítani. Mármost találunk olyan
(
x
,
y
)
-élt, melyet csak két háromszög
tartalmaz. Hiszen legyen
x
valamely
T
háromszög belsejében lévő pont (minden
pont rendelkezik ezzel a tulajdonsággal, amely nem a
legkülső háromszögön van) és válasszuk
x
-et és
T
-t úgy, hogy a
T
belsejében lévő lapok száma minimális
legyen. Legyen
y
az
x
bármely szomszédja. Ha
(
x
,
y
)
három háromszögnek, mondjuk
(
x
,
y
,
z
1
)
-nek,
(
x
,
y
,
z
2
)
-nek és
(
x
,
y
,
z
3
)
-nak is éle lenne, akkor ezen
háromszögek mind
T
belsejének valódi részei lennének, és
mondjuk
(
x
,
y
,
z
1
)
a belsejében tartalmazná
z
3
-at,
T
minimalitásával ellentétben.
Így válasszunk egy
(
x
,
y
)
-élt, melyre
(
x
,
y
)
-éle csak a vele szomszédos
(
x
,
y
,
z
1
)
és
(
x
,
y
,
z
2
)
háromszögeknek van. Húzzuk össze
(
x
,
y
)
-t a
p
pontba és hagyjunk el egy élt mindkét
előálló párhuzamos élpárból. Így egy új
G
0
egyszerű háromszögelt síkgráfot
kapunk, és az indukciós feltétel miatt van olyan
G
0
′
háromszögelt síkgráf egyenes élekkel,
hogy
G
0
és
G
0
′
lapjai egymásnak
megfeleltethetők.
Tekintsük a
G
0
′
(
p
,
z
1
)
-nek és
(
p
,
z
2
)
-nek megfelelő éleit. A
p
körüli szöget két szögre osztják; ezek
egyike tartalmazza azon éleket, melyek elő-képei
G
-ben szomszédosak
x
-szel, a másik azokat, melyek
elő-képei szomszédosak
y
-nal. Így „
x
-et és
y
-t széthúzhatjuk” és
G
egy megfelelő egyenes élekkel
rendelkező reprezentációját kapjuk (38. ábra). [K.
Wagner–Fáry I.].