- 1. feladat F Ö
Először legyen
F
1
egy
ϱ
(
G
)
elemű élrendszer, mely minden pontot
lefed. Mivel
F
1
egy éle lehagyásával lesz le nem
fedett pont, minden
F
1
-beli élnek van olyan végpontja,
melynek fokszáma
〈
V
(
G
)
,
F
1
〉
-ben 1. Ebből az következik, hogy
F
1
diszjunkt csillagokból áll.
〈
V
(
G
)
,
F
1
〉
komponenseinek száma nyilvánvalóan
V
(
G
)
−
F
1
=
V
(
G
)
−
ϱ
(
G
)
. Válasszunk a
〈
V
(
G
)
,
F
1
〉
minden komponenséből egy élt. Ekkor
V
(
G
)
−
ϱ
(
G
)
független élünk lesz, ami miatt
Másrészről legyen
F
2
egy
ν
(
G
)
elemű független élrendszer. Válasszunk
egy élt a
V
(
G
)
−
2
ν
(
G
)
F
2
által le nem fedett pontok
mindegyikéről.
F
2
-vel együtt ezek az élek
G
összes pontját lefedik, és a számuk
ami miatt
(1) és (2) a kívánt egyenlőséget adja. [T.
Gallai, Ann. Univ. Sci. R. Eötvös, Sectio Math. 2
(1959) 133–138.]
- 2. feladat F Ö
Első megoldás. Legyen
{
A
,
B
}
a
G
egy 2-színezése, azaz tegyük fel, hogy
V
(
G
)
=
A
∪
B
,
A
∩
B
=
∅
és
G
minden éle
A
-beli pontot
B
-belivel köt össze. Tekintsünk két új
a
,
b
pontot. Kössük össze
a
-t
A
minden pontjával és
b
-t
B
minden pontjával. Legyen
G
′
az eredményül kapott gráf. Vegyük
észre, hogy
(i) egy
S
⊆
V
(
G
)
halmaz akkor és csak akkor fogja le
(
a
,
b
)
-t
G
′
-ben, ha
S
lefogja
G
minden élét,
(ii) a független
(
a
,
b
)
-utak maximális száma
ν
(
G
)
;
G
bármely
ν
(
G
)
független éle
ν
(
G
)
független
(
a
,
b
)
-utat ad, és megfordítva, bármely
k
független
(
a
,
b
)
-út tartalmaz
k
független
G
-beli élt.
Mivel a Menger-tétel szerint az
(
a
,
b
)
-t lefogó halmazok minimális mérete
egyenlő a független
(
a
,
b
)
-utak maximális számával, (i) és (ii)
bizonyítja, hogy
ν
(
G
)
=
τ
(
G
)
. Mivel 7.1 szerint
ν
(
G
)
+
ϱ
(
G
)
=
V
(
G
)
és nyilvánvalóan
α
(
G
)
+
τ
(
G
)
=
V
(
G
)
, a feladat másik egyenlőtlensége
azonnal adódik.
Második megoldás. Megmutatjuk, hogy
ν
(
G
)
=
τ
(
G
)
. Mivel az magától értetődő, hogy
ν
(
G
)
≤
τ
(
G
)
, elég azt belátni, hogy
ν
(
G
)
≥
τ
(
G
)
.
Legyen
G
′
a
G
azon minimális részgráfja, melyre
τ
(
G
′
)
=
τ
(
G
)
. Megmutatjuk, hogy ekkor
G
′
diszjunkt élekből áll. Ez azért lesz
elég, mert az élek száma
τ
(
G
′
)
=
τ
(
G
)
kell, hogy legyen, így
ν
(
G
)
≥
τ
(
G
)
következik.
Indirekte tegyük fel, hogy van egy olyan
x
pont, mely a
G
′
e
1
=
(
x
,
y
1
)
,
e
2
=
(
x
,
y
2
)
éleihez illeszkedik.
G
′
minimalitása miatt van egy olyan
S
i
halmaz, melyre
S
i
=
τ
(
G
)
−
1
és mely lefogja
G
′
−
e
i
(
i
=
1
, 2) minden élét. Természetesen
x
,
y
i
∉
S
i
, de
y
1
∈
S
2
,
y
2
∈
S
1
. Legyen
R
=
S
1
∩
S
2
,
R
=
p
,
τ
(
G
)
=
t
, és jelöljük
G
1
-gyel a
G
′
(
S
1
−
R
)
∪
(
S
2
−
R
)
∪
{
x
}
által feszített részgráfját.
Mivel
G
1
a
G
részgráfja, így páros. Legyen
{
A
,
B
}
a
G
1
2-színezése, és mondjuk
A
≤
B
. Ekkor
Azt állítjuk, hogy
A
∪
R
le
G
′
minden élét. Legyen
e
∈
E
(
G
′
)
. Ha
e
-nek van végpontja
R
-ben, akkor készen vagyunk.
Megmutatjuk, hogy ha
e
-t
R
nem fogja le, akkor
G
1
-be tartozik. Ez nyilvánvaló, ha
e
=
e
i
, mivel
x
,
y
i
∈
V
(
G
1
)
. Ha
e
≠
e
i
, akkor mind
S
1
−
R
, mind
S
2
−
R
le kell, hogy fogja
e
-t, és így
e
-nek
S
1
−
R
-t és
S
2
−
R
-t kell összekötnie. Tehát
e
mindkét végpontja ismét
V
(
G
1
)
-beli. Mivel
A
lefogja
G
1
minden élét, így lefogja
e
-t is.
Tehát
τ
(
G
′
)
≤
A
∪
R
=
t
−
p
−
1
+
p
=
t
−
1
, ami ellentmond
G
′
definíciójának [D. Kőnig; lásd bármely
gráfelméleti tankönyvben].
- 3. feladat F Ö
I. Tegyük fel, hogy az
F
valamely
x
pontja össze van kötve egy
y
∈
B
1
ponttal. Ekkor természetesen
x
∈
A
. (
∗
∗
) szerint van egy
F
-beli
P
út, mely
x
-et egy
a
∈
A
1
ponthoz köti. Ez az út
a
-ból nem
M
-beli élen indul. Tehát (
∗
) miatt a második éle
M
-beli. A harmadik éle ennélfogva nem
M
-beli, míg (
∗
) miatt a negyedik éle ismét
M
-beli, stb. Tehát ez egy
M
-re vonatkozó alternáló út, melynek
utolsó éle
M
-beli. Cseréljük fel
E
(
P
)
∩
M
és
E
(
P
)
−
M
éleit, ekkor egy olyan
M
′
párosítást kapunk, melyhez
(
x
,
y
)
hozzávehető. Tehát
M
nem maximális párosítás.
II. Másfelől tegyük fel, hogy egyetlen
F
-beli pont sem szomszédos egyetlen
B
1
-beli ponttal sem. Legyen
X
=
A
−
V
(
F
)
és
Y
=
V
(
F
)
∩
B
. Azt állítjuk, hogy
X
∪
Y
=
M
és
X
∪
Y
lefog minden élt.
X
∪
Y
minden pontját lefedi
M
, hiszen tegyük fel, hogy ez nem így
van. Ha
y
∈
Y
=
V
(
F
)
∩
B
, akkor (
∗
) miatt
y
-t lefedi
M
. Ha
x
∈
X
=
A
−
V
(
F
)
és
x
∈
A
1
, akkor az
F
′
=
F
∪
{
x
}
erdő nagyobb
F
-nél, ellentmondva annak a
feltételnek, hogy
F
maximális
M
-re nézve.
Továbbá egyetlen
M
-beli él sem fedi
X
∪
Y
két pontját, mert ha
(
x
,
y
)
∈
M
és
y
∈
V
(
F
)
∩
B
, akkor
x
∈
V
(
F
)
az
F
maximalitása miatt. Ennélfogva
X
∪
Y
=
M
.
Másodszor legyen
(
u
,
v
)
egy
X
∪
Y
által le nem fedett él és tegyük fel,
hogy
u
∈
A
,
v
∈
B
. Ekkor
u
∈
V
(
F
)
és
v
∉
V
(
F
)
. Továbbá a feltétel szerint
v
∉
B
1
. Tehát van egy
(
w
,
v
)
∈
M
,
w
≠
u
él, mivel
X
∪
Y
=
M
. Itt
w
∈
V
(
F
)
, mert különben ugyanúgy, mint az I.
részben az következne, hogy
w
F
-ben
A
1
-hez lenne kötve egy
w
-ből
(
w
,
v
)
-n induló úttal, ami miatt
v
∈
V
(
F
)
, ez pedig ellentmondás. De ha
w
∈
V
(
F
)
, akkor az
(
u
,
v
)
és
(
w
,
v
)
élek hozzávehetők
F
-hez, ami ellentmond
F
maximalitásának.
Tehát
τ
(
G
)
≤
M
. Mivel az nyilvánvaló, hogy
M
≤
ν
(
G
)
≤
τ
(
G
)
, azonnal adódik, hogy
Az első egyenlőtlenség mutatja, hogy
M
maximális párosítás. A második
bizonyítja Kőnig tételét.
A kívánt algoritmus a következő lehet: Induljunk
ki egy
M
párosításból. Hozzunk létre a (
∗
) és (
∗
∗
) feltételeknek megfelelő erdőt. Ekkor
vagy növelhetjük
M
-et, vagy levonhatjuk a
következtetést, hogy
M
maximális párosítás. Az utóbbi esetben
egyben egy minimális fedőrendszert is kapunk.
Nem megyünk bele a részletekbe, de megjegyezzük,
hogy az algoritmus időigénye a pontok számában
polinomrendű.
- 4. feladat F Ö
(a) Első megoldás. Azt akarjuk bebizonyítani,
hogy
ν
(
G
)
=
A
. A 7.2 feladat szerint elég azt
belátni, hogy
ν
(
G
)
=
A
. Mivel
A
lefogja az összes élt,
τ
(
G
)
≤
A
. Tehát elég azt megmutatni, hogy
bármely minden élt lefogó
S
halmaz legalább
A
elemű. Vegyük észre, hogy ha
S
lefogja
G
minden élét, akkor
mert ha
x
∈
A
−
S
össze van kötve
y
∈
B
-vel, akkor az
(
x
,
y
)
él lefogásához
S
-nek tartalmaznia kell
y
-t. Tehát a tétel feltevése szerint
és így
Második megoldás. Indukciót alkalmazunk
A
-ra. Két esetet különböztetünk
meg:
1. eset: Van olyan
A
1
⊂
A
,
A
1
≠
∅
halmaz, melyre
Γ
(
A
1
)
=
A
1
. Legyen
G
1
a
G
A
1
∪
Γ
(
A
1
)
által feszített részgráfja és legyen
G
2
=
G
−
A
1
−
Γ
(
A
1
)
. Azt állítjuk, hogy mind
G
1
, mind
G
2
kielégíti a feladat
feltételeit.
Legyen
X
⊆
A
1
. Ekkor
Γ
(
X
)
⊆
Γ
(
A
1
)
, és így
Másrészről tegyük fel, hogy
X
⊆
A
−
A
1
. Ekkor
Tehát az indukciós feltevés szerint létezik egy
G
1
-beli
F
1
párosítás, mely mely párosítja
A
1
-et
Γ
(
A
1
)
-gyel, és egy
G
2
-beli
F
2
párosítás, mely párosítja
A
−
A
1
-et
B
−
Γ
(
A
1
)
valamely pontjaival.
F
1
∪
F
2
egy keresett párosítás.
2. eset:
Γ
(
X
)
>
X
minden
X
⊂
A
,
X
≠
∅
-ra. Legyenek
x
∈
A
és
y
∈
B
szomszédos pontok. Azt állítjuk, hogy
G
1
=
G
−
x
−
y
kielégíti a feladat feltételeit.
Legyen
X
⊆
A
−
{
x
}
; ha
X
=
∅
, akkor
Γ
(
X
)
=
0
=
X
, így feltehetjük, hogy
X
≠
∅
. Azt is tudjuk, hogy
X
≠
A
, így a feltétel szerint
Γ
(
X
)
>
X
. Tehát
Így az indukciós feltevés szerint van olyan
F
1
párosítás
G
1
-ben, mely lefedi
A
−
{
x
}
minden pontját. Most
F
1
∪
{
(
x
,
y
)
}
egy kívánt típusú párosítás.
(b) Ha
G
-ben van 1-faktor, akkor nyilvánvaló, hogy
Megfordítva, ha (3) fennáll, akkor (a)-ból
következik, hogy
G
-ben van 1-faktor. [P. Hall]
- 5. feladat F Ö
7.2 miatt elég azt belátni, hogy
Először legyen
X
⊆
A
olyan halmaz, melyre
Legyen
S
=
Γ
(
X
)
∪
(
A
−
X
)
. Ekkor
S
lefogja
G
minden élét, és így
Legyen
S
minimális lefogó pont-rendszer és
X
=
A
−
S
. Ekkor úgy, mint korábban,
és így
ami miatt
[O. Ore]
- 6. feladat F Ö
(a) Az ötlettár észrevétele szerint
Másrészről
(
∗
) miatt és mivel
X
1
∩
X
2
≠
∅
. Tehát
Mivel mindenhol egyenlőségnek kell lenni,
így speciálisan
(b) Legyen
G
1
az ötlettár szerint definiált. Legyen
x
∈
A
, és legyen
S
az összes olyan
X
halmaz metszete, melyre
Ekkor (a) ismételt alkalmazásával azt
látjuk, hogy
S
önmaga kielégíti ugyanezt a feltételt:
(Ha az állítás igaz, akkor
S
=
{
x
}
, de ezt most még nem
tudhatjuk.)
Legyen
y
tetszőleges
x
-szel szomszédos pont. Mivel
G
1
−
(
x
,
y
)
nem rendelkezik a (2) tulajdonsággal,
találunk egy olyan
X
⊆
A
,
X
≠
∅
halmazt, melyre
De mert másrészről
Γ
G
1
−
(
x
,
y
)
(
X
)
csak 1-gyel különbözhet
Γ
G
1
(
X
)
-től, azt kapjuk, hogy
Így
S
definíciója szerint
S
⊆
X
, és
mert
Mivel (5) az
x
minden
y
szomszédjára fennáll, azt kapjuk, hogy
Tehát
Itt
és
Következésképpen
Ezt (1)-nal összevetve látjuk, hogy
mindenhol egyenlőségnek kell állni, speciálisan (6)-ben
is. [L. Lovász, Acta Math. Acad. Sci. Hung. 21 (1970)
443–446.]
- 7. feladat F Ö
(i)
⇒
(iii).
G
-ben van 1-faktor, így
A
=
B
. Legyen
∅
≠
X
⊂
A
, és indirekte tegyük fel, hogy
Γ
(
X
)
≤
X
. Itt egyenlőségnek kell lenni, mert
G
-ben van 1-faktor. Másrészt
X
∪
Γ
(
X
)
legalább egy
e
éllel kapcsolódik a gráf többi
részéhez, mert
G
összefüggő. Nyilvánvaló, hogy
e
Γ
(
X
)
-et
A
−
X
-szel köti össze. Ezt az
e
élt egyetlen 1-faktor sem tartalmazza;
hiszen ha
F
1-faktor, akkor
X
számú
X
-et elhagyó élt tartalmaz. De ezen
élek lefedik
Γ
(
X
)
egészét, így
e
nem tartozhat
F
-be.
(iii)
⇒
(ii). Azt kell megmutatnunk, hogy
G
−
x
−
y
-ben van 1-faktor, ha
x
∈
A
,
y
∈
B
. Mivel
A
−
{
x
}
=
B
−
{
y
}
, elég azt belátni, hogy van
G
−
x
−
y
-ben
A
−
{
x
}
-et lefedő párosítás. De ez ekvivalens
azzal, hogy minden
X
⊆
A
−
{
x
}
-re
Ez nyilvánvaló, ha
X
=
∅
. Különben
(ii)
⇒
(i). Tegyük fel, hogy
G
nem összefüggő. Ekkor találunk olyan
G
1
komponenst, melyre
V
(
G
1
)
∩
A
≤
V
(
G
1
)
∩
B
. Legyen
x
∈
V
(
G
1
)
∩
A
,
y
∈
B
−
V
(
G
1
)
. Ekkor
G
−
x
−
y
-ben nem lehet 1-faktor, mert
V
(
G
1
)
∩
B
csak a
V
(
G
1
)
∩
A
−
1
<
V
(
G
1
)
∩
B
pontokkal szomszédos. Tehát
G
összefüggő.
Legyen
e
=
(
x
,
y
)
a
G
tetszőleges éle. Ekkor
G
−
x
−
y
-ben van 1-faktor, mely a
kiterjeszthető
G
egy
e
-t tartalmazó 1-faktorává. Tehát
G
minden élét tartalmazza valamely
1-faktor. [G. Hetyei, Pécsi Tan. Főisk. Közl. (1964)
151–168.]
- 8. feladat F Ö
I. Először megmutatjuk, hogy az
alakú gráfok, ahol
P
1
,
…
,
P
k
-t a feladatban leírtak szerint
választjuk, mind elemi gráfok. Természetesen párosak és
összefüggőek.
Indukciót alkalmazunk
k
-ra. Tegyük fel, hogy
elemi és legyen
x
,
y
a
P
k
két végpontja. Vegyük észre először,
hogy
G
′
minden 1-faktora kiterjeszthető
G
1-faktorává, egyszerűen
P
k
minden második élének hozzáadásával, a
második éllel kezdve. Tehát
G
′
minden élét ugyanúgy, mint
P
k
minden második élét tartalmazza
G
valamely 1-faktora.
Másfelől
G
′
−
x
−
y
-ben van egy
F
0
1-faktor. Vegyük hozzá
F
0
-hoz
P
k
minden második élét az első éllel
kezdve. Ekkor a
G
egy olyan 1-faktorát kapjuk, mely
tartalmazza
P
k
eddig fel nem használt éleit.
Tehát bebizonyítottuk, hogy
G
összefüggő és minden élét tartalmazza
valamely 1-faktora. Ez az előző eredmény szerint
bizonyítja, hogy elemi gráf.
II. Tegyük fel, hogy
G
elemi gráf. Legyen
F
a
G
egy 1-faktora és legyen
G
0
az
F
egy éle által alkotott gráf. Egyenként
választjuk ki a
P
1
,
P
2
,
…
,
P
k
utakat úgy, hogy rendelkezzenek a
feladatban megkövetelt tulajdonságokkal, és ezen
felül
(
∗
)
F
-re nézve alternáló utak, melyek nem
F
-beli éllel kezdődnek (megengedjük,
hogy
P
i
egyetlen nem
F
-beli élből álljon).
Tegyük fel, hogy
P
1
,
…
,
P
i
-t már kiválasztottuk, és
G
′
=
G
0
∪
…
∪
P
i
≠
G
. Legyen
e
egy nem
G
′
-beli él, melynek legalább egyik
x
végpontja
G
′
-beli. Mivel
G
összefüggő, ilyen él létezik. Legyen
F
1
a
G
egy
e
-t tartalmazó 1-faktora.
Vegyük észre, hogy a (
∗
) pótlólagos feltétel miatt,
G
′
rendelkezik azzal a tulajdonsággal,
hogy
F
∩
E
(
G
′
)
a
G
′
egy 1-faktora, és
F
0
=
F
−
E
(
G
′
)
egyáltalán nem érinti
G
′
-t. Tehát ha tekintjük
F
1
∪
F
0
-t, ennek egyik komponense egy
e
-vel végződő út lesz. Ezen
P
i
+
1
útnak mindkét végpontja
G
′
-beli lesz (egyikük
x
) és nem lesz más
G
′
-beli pontja. A végső élei
F
1
-beliek, és így paritás-megfontolások
miatt
P
i
+
1
páratlan hosszú, és a
G
′
különböző osztályába tartozó pontokat
köt össze. Definíciója szerint
F
-re nézve a megfelelő módon alternáló
út. Így ha
G
0
∪
P
1
∪
…
∪
P
i
≠
G
, ezt az uniót kiterjeszthetjük
P
i
+
1
-vel. Előbb-utóbb kimerítjük
G
-t, ami bizonyítja az állítást. [G.
Hetyei, uo.]
- 9. feladat F Ö
Reprezentáljuk
G
-t a következő alakban:
az előző feladatnak megfelelően. Itt
P
k
nem lehet egyetlen él, mert
elemi gráf, így nem állhat elő
G
-ből egyetlen él eltávolításával.
Tehát
P
k
-nak van belső pontja (valójában
legalább kettő), és ezek fokszáma 2. [G. Hetyei,
uo.].
Az az erősebb állítás, miszerint minden élnek van
másodfokú végpontja, hamis. Az 54. ábrán látható gráf
előáll a 7.8 konstrukcióval, így elemi gráf, és
minimális is. Ennek bizonyításához megjegyezzük, hogy
elemi gráf fokszáma 7.7 szerint legalább 2. Bármely
e
-től és
f
-től különböző él elhagyásával a
kapott gráfban lesz elsőfokú pont, így már nem lehet
elemi. Ha
e
vagy
f
az elhagyott él, akkor az
x
vagy
O
jelű három pont csak három ponttal
lesz szomszédos, ami 7.7 szerint ismét azt mutatja,
hogy a kapott gráf nem elemi. Viszont
e
mindkét végpontja harmadfokú. [J.
Csima].
- 10. feladat F Ö
Először tegyük fel, hogy
G
r
-reguláris. Megmutatjuk, hogy ekkor
G
-ben van 1-faktor. Nyilvánvaló, hogy
ami miatt
A
=
B
.
Tehát elég azt belátni, hogy
G
tartalmaz
A
-t lefedő párosítást, vagy 7.4 miatt
azt, hogy minden
X
⊆
A
-ra
Tegyük fel, hogy
X
⊆
A
, és számoljuk meg az
X
-et elhagyó éleket. A regularitás
miatt
r
X
ilyen él van. Másrészről ezek
mindegyike egy
Γ
(
X
)
-beli pontba megy, és
Γ
(
X
)
minden pontja közülük legfeljebb
r
-et érint. Ennélfogva
Tehát
G
-ben van 1-faktor.
Legyen
F
a
G
1-faktora.
G
−
F
egy
(
r
−
1
)
-reguláris páros gráf, és indukcióval
r
−
1
darab 1-faktor uniójára esik szét.
F
-et ezekhez hozzávéve egy kívánt
dekompozíciót kapunk.
Legyen most
G
tetszőleges gráf, melynek maximális
fokszáma
r
. Vegyünk fel új (izolált) pontokat,
hogy
G
két szín-osztálya egyenlő nagy legyen.
Ezután vegyünk fel új éleket egészen addig, amíg a
maximális fokszámot nem növeljük meg. Az ily módon
kapott
G
1
gráf
r
-reguláris lesz; hiszen ha lenne egy
d
G
1
(
x
)
<
r
fokszámú
x
pont, akkor az ellentétes szín-osztály
szintén tartalmazna egy ilyen
y
pontot, és az
(
x
,
y
)
-élt még felvehetnénk (többszörös élek
nincsenek kizárva!).
Tehát
G
1
r
-reguláris,
G
-t tartalmazó gráf lesz. Így
feloszthatjuk
G
1
-et
r
1-faktorra, ezzel
G
egy
r
párosításra való felbontását is
előállítva.
- 11. feladat F Ö
Jelölje
G
1
az ötlet szerint előállított páros
gráfot. Ekkor
és így az előző feladat miatt
E
(
G
1
)
az
F
1
,
…
,
F
k
párosítások uniója lesz.
Azonosítsuk
G
1
azon pontjait, melyek
G
ugyanazon pontjának felelnek meg,
ekkor
F
1
,
…
,
F
k
-t valamely
F
1
′
,
…
,
F
k
′
részgráfokra képezzük le. Mivel
F
i
párosítás, legfeljebb egy-egy
F
i
-él szomszédos a
G
1
bármely
x
∈
V
(
G
)
-nek megfelelő
d
(
x
)
k
pontjával. Ennélfogva
Másrészről
G
1
-ben
d
(
x
)
k
darab
x
-nek megfelelő pontja fokszáma
k
. Ezek mindegyikéből kell, hogy
induljon
F
i
-beli él, ami miatt
[D. de Werra].
- 12. feladat F Ö
7.11 szerint
G
-nek van olyan
G
1
∪
…
∪
G
r
felbontása, hogy
minden
x
pont esetén. Mivel
d
(
x
)
≥
r
az
r
definíciója szerint, ebből az
következik, hogy
azaz
G
i
egy él-fedés [R. P. Gupta, Theory of
Gr. Int. Symp. Rome, Dunod, Paris–Gordon and Breach,
New York, (1967) 135–138].
- 13. feladat F Ö
Legyen
G
1
az ötlettárban definiált, 1-faktort
nem tartalmazó gráf. Legyen
{
A
,
B
}
a
G
egy 2-színezése, természetesen
A
=
B
. Így ha
G
1
-ben nincsen 1-faktor, 7.4b-ből az
következik, hogy létezik egy
X
⊆
A
, melyre
Megszámoljuk
G
X
-et elhagyó éleit két különböző
módszerrel. Először ezen élek száma
r
⋅
X
. Másodszor legfeljebb
X
⋅
(
n
−
Γ
G
1
(
X
)
)
él köti össze
X
-et
B
−
Γ
G
1
(
X
)
-szel (mivel ezek egyszerű élek) és
legfeljebb
r
⋅
Γ
G
1
(
X
)
él köti össze
X
-et
Γ
G
1
(
X
)
-vel, mivel
Γ
G
1
(
X
)
bármely pontjának fokszáma
r
. Tehát
vagy ezzel ekvivalensen
Minket nyilvánvalóan az
r
>
n
eset érdekel, különben még többszörös
élek létezése sem következik. Ekkor
X
<
r
, és (7), (8) azt vonja maga után,
hogy
vagy, ami ezzel ekvivalens:
Így megmutattuk, hogy
r
>
n
+
1
2
⋅
n
+
2
2
egy
G
1
-beli 1-faktor létezését vonja maga
után.
Megfordítva, legyen
A
=
B
=
n
,
A
′
⊂
A
,
A
′
=
n
+
1
2
,
B
′
⊂
B
és
B
′
=
n
−
1
2
. Kössük
A
′
minden pontját
B
′
minden pontjához
n
+
2
2
éllel,
A
−
A
′
minden pontját
B
−
B
′
minden pontjához
n
+
1
2
éllel; és
A
′
minden pontját
B
−
B
′
minden pontjához egy éllel. A kapott
G
gráf
n
+
1
2
⋅
n
+
2
2
-reguláris. Bármely
r
≤
n
+
1
2
⋅
n
+
2
2
esetén
G
tartalmaz egy
r
-reguláris
G
r
feszítő részgráfot (lásd 7.10). Vegyük
észre, hogy
G
sem, és ebből következően
G
r
sem tartalmaz olyan 1-faktort, mellyel
párhuzamos élek vannak
G
r
-ben. Ez bizonyítja, hogy
r
(
n
)
=
n
+
1
2
⋅
n
+
2
2
+
1
.
- 14. feladat F Ö
I. Megmutatjuk, hogy nem akadhatunk el más
helyzetben, mint mikor
x
=
a
1
és
a
1
össze van kötve valamely
b
i
-vel
r
párhuzamos éllel.
Tegyük fel, hogy akkor akadunk el, amikor
x
=
b
i
. Amiért nem tudjuk folytatni, az az,
hogy
a
μ
-ből érkeztünk (
1
≤
μ
≤
n
), és
b
i
-nek nincsen szomszédja
a
μ
-n kívül. Mivel
b
i
fokszáma
r
−
1
, amikor
x
=
b
i
, akkor
r
−
1
db.
(
a
μ
,
b
i
)
-élnek kell lenni. Így az előző
lépésben, amikor
x
=
a
μ
volt,
r
db.
(
a
μ
,
b
i
)
-él volt. Tegyük fel, hogy
x
a
μ
-be
b
j
≠
b
i
-ből érkezett. Ekkor az
(
a
μ
,
b
j
)
-él megduplázódott, azaz
a
μ
fokszáma legalább
r
+
2
volt, ami nincs megengedve.
Hasonlóan kapjuk azt, hogy ha akkor akadunk el,
amikor
x
=
a
i
, akkor
i
=
1
, és a kívánt helyzetben
vagyunk.
II. Így már csak azt kell megmutatni, hogy az
eljárás nem futhat a végtelenségig. Indirekte tegyük
fel, hogy végtelen. Megjegyezzük, hogy minden előálló
gráf minden éle párhuzamos
G
éleivel. Tekintsük
G
azon éleit, melyeken
x
végtelen sokszor halad át. Ezen éleken
mindkét irányban végtelen sokszor kell áthaladnia,
különben a multiplicitásuk
+
∞
-hez vagy
−
∞
-hez tartana, de mindkét eset
lehetetlen.
Tekintsünk egy
b
i
pontot, és tegyük fel, hogy 3 rá
illeszkedő élt,
(
a
μ
,
b
i
)
-t,
(
a
ν
,
b
i
)
-t és
(
a
ϱ
,
b
i
)
-t végtelen sokszor használunk (
μ
<
ν
<
ϱ
≤
n
). Ekkor
(
a
ϱ
,
b
i
)
-n sohasem haladhatnánk át
b
i
-ből
a
ϱ
-ba, mivel vagy
(
a
μ
,
b
i
)
vagy
(
a
ν
,
b
i
)
mindig egy
μ
,
ν
<
ϱ
választás. Ez viszont lehetetlen.
Hasonlóan következik, hogy minden
a
μ
legfeljebb két végtelen sokszor
használt éllel szomszédos.
Tekintsünk egy olyan fázist, amikor már minden
véges sokszor használt élt elhasználtunk. Mivel minden
pont legfeljebb két végtelen sokszor használt éllel
szomszédos,
x
csak egy kör mentén mozoghat. De akkor
ezen kör élein mindig ugyanabban az irányban haladunk
át, ami ellentmondás.
Az eljárás így egy
r
-reguláris gráfot eredményez, melyet a
G
egy részgráfjából kapunk az élek
többszörözésével, és melyben az
{
a
1
,
b
i
}
pár egy komponenst feszít ki.
Megismételve végül is egy olyan gráfot kapunk, mely a
G
egy 1-faktorából úgy áll elő, hogy
minden élét
r
-szer vesszük. Tehát a
G
egy 1-faktorát kapjuk. Vegyük észre,
hogy elegendő az aktuális él-listát és még egy plusz
pontot tárolni; az eljárást a táblán szivacs és kréta
segítségével végigvezethetjük. [J. Csima; lásd
J. Csima–L. Lovász,
Discrete Appl. Math.
35,
197–203.]
- 15. feladat F Ö
(a) Szimultán indukciót alkalmazunk
V
(
G
)
-re és
k
-ra.
Először tegyük fel, hogy
G
elemi. Legyenek
x
∈
A
és
y
∈
B
szomszédosak. Ekkor a
G
(
x
,
y
)
-t tartalmazó 1-faktorai megfelelnek a
G
−
x
−
y
1-faktorainak. Mivel
(
x
,
y
)
-t tartalmazza valamely 1-faktor,
(
G
−
x
−
y
)
-ban is van 1-faktor. Továbbá
A
−
x
minden pontjának fokszáma
(
G
−
x
−
y
)
-ban legalább
k
−
1
, így az indukciós feltevés szerint
(
G
−
x
−
y
)
-ban legalább
(
k
−
1
)
!
1-faktor van. Tehát
G
minden élét legalább
(
k
−
1
)
!
1-faktor tartalmazza.
Rögzítsük
x
∈
A
-t. Legalább
k
él szomszédos
x
-szel, és ezek mindegyikét legalább
(
k
−
1
)
!
1-faktor tartalmazza. Ezzel
k
(
k
−
1
)
!
=
k
!
1-faktort kapunk, melyek nyilvánvalóan
különbözők.
Tegyük fel, hogy
G
nem elemi. Ekkor 7.7 szerint létezik
olyan
∅
≠
X
⊂
A
, melyre
Legyen
F
a
G
tetszőleges 1-faktora és legyen
F
1
az (
A
−
X
)-ből induló éleinek halmaza. Ekkor
nyilvánvaló, hogy
F
többi éle lefedi
Γ
(
X
)
-et, így
F
1
(
A
−
X
)-et (
B
−
Γ
(
X
)
)-szel párosítja.
Vegyük észre, hogy az
X
∪
Γ
(
X
)
által feszített
G
1
részgráf ugyanazokat a követelményeket
elégíti ki, mint
G
:
X
minden pontjának fokszáma legalább
k
G
1
-ben, és van benne 1-faktor (pl.
F
−
F
1
). Ennélfogva
G
1
-ben legalább
k
!
1-faktor van az indukciós feltevés
miatt. Hozzávéve
F
1
-et minden ilyen 1-faktorhoz,
k
!
1-faktort kapunk
G
-ben [M. Hall, Bull Amer. Math. Soc.
54 (1948) 922–926].
(b) Indukciót alkalmazunk
m
−
n
+
2
-re. Ha ez a szám
2
, akkor
G
egyetlen körből áll és az állítás
triviális. Tegyük fel, hogy
m
>
n
, ekkor 7.8 szerint
ahol
G
1
elemi páros gráf és
P
páratlan út, melynek csak az
x
,
y
végpontjai közösek
G
1
-gyel, és
x
,
y
a
G
1
különböző szín-osztályaiba tartoznak.
Nyilvánvaló, hogy
így tehát az indukciós feltevés miatt
G
1
legalább
m
−
n
+
1
darab 1-faktort tartalmaz. Ezek
mindegyike kiterjeszthető egy
G
-beli 1-faktorrá. Továbbá 7.7 miatt
G
1
−
x
−
y
is tartalmaz egy 1-faktort, mely
szintén kiterjeszthető a
G
egy 1-faktorává
P
minden második élét használva. Tehát
valóban találtunk
(
m
−
n
+
1
)
+
1
=
m
−
n
+
2
1-faktort
G
-ben [vö. L. Lovász–M. D. Plummer,
Infinite and Finite Sets, Coll. Math. Soc. J. Bolyai
10, Bolyai–North-Holland (1975), 1051–1079].
- 16. feladat F Ö
I. Tegyük fel, hogy
G
-ben van egy
F
f
-faktor. Ekkor nyilvánvaló, hogy
mely (i)-t bizonyítja. Legyen
X
⊂
A
és
Y
⊆
B
. Ekkor legfeljebb
m
(
X
,
Y
)
F
-beli él köti össze
X
-et és
Y
-t, és legfeljebb
∑
y
∈
B
−
y
f
(
y
)
F
-beli él köti
X
-et
B
−
Y
-hoz. Mivel pontosan
∑
x
∈
X
f
(
x
)
F
-beli él köti
X
-et
B
-hez, ebből (ii) már
következik.
II. Tegyük fel, hogy (i) és (ii) teljesül.
Irányítsunk minden élt
A
-ból
B
-be. Vegyünk két pontot,
a
-t és
b
-t, és kössük
a
-t minden
A
-beli ponthoz, és
B
minden pontját
b
-hez irányított éllel. Definiáljuk a
c
(
e
)
kapacitást egy
e
élen a kapott
G
0
irányított gráfban a következők szerint:
Vegyük észre, hogy
G
0
-ban akkor és csak akkor van
∑
x
∈
A
f
(
x
)
=
∑
y
∈
B
f
(
y
)
értékű
(
a
,
b
)
-folyam, ha
G
-ben van
f
-faktor. Tehát 6.74 és 6.77 miatt azt
kell belátnunk, hogy
G
0
minden
(
a
,
b
)
-vágásának kapacitása legalább
∑
x
∈
A
f
(
x
)
.
Legyen
S
egy
(
a
,
b
)
-vágást meghatározó halmaz (
a
∈
S
⊂
V
(
G
0
)
),
X
=
S
∩
A
és
Y
=
B
−
S
. Ekkor az
S
által meghatározott vágás kapacitása
(ii) szerint [O. Ore,
D. Gale–H. J. Ryser].
- 17. feladat F Ö
Tegyük fel, hogy
G
egy
G
′
d
-reguláris páros gráfba van ágyazva,
melynek szín-osztályai
A
és
B
. Legyen
A
1
=
A
∩
V
(
G
)
,
B
1
=
B
∩
V
(
G
)
,
A
2
=
A
−
A
1
,
B
2
=
B
−
B
1
. Mivel
G
′
-nek pontosan
d
−
d
(
x
)
éle köti
x
-et
B
2
-höz bármely
x
∈
A
1
-re, azt kapjuk, hogy
vagy ezzel ekvivalens alakban
Hasonlóan
Összeadva azt kapjuk, hogy
tehát
és minthogy
V
(
G
′
)
páros egész szám,
A következő lépés annak bizonyítása, hogy
G
beágyazható feszített részgráfként egy
G
′
d
-reguláris páros
2
n
−
2
m
d
pontú gráfba. Legyen
{
A
,
B
}
a
G
egy 2-színezése. Mivel
m
≤
d
⋅
A
és
m
≤
d
⋅
B
, ezért
Így konstruálhatunk két diszjunkt
A
′
⊃
A
,
B
′
⊃
B
halmazt, melyre
Felveszünk még
(
A
,
B
′
−
B
)
-éleket és
(
B
,
A
′
−
A
)
-éleket úgy, hogy
A
∪
B
-ben minden fokszám egyenlő legyen
d
-vel. Ez lehetséges, mert
és hasonlóan
(és mert többszörös éleket megengedünk).
Végül felveszünk még
(
A
′
−
A
,
B
′
−
B
)
-éleket, hogy minden fokszám
d
legyen.
- 18. feladat F Ö
Tekintve
G
-nek az ötlettárban leírt
G
˜
„páros komplementerét”, 7.16 szerint
elég megmutatni, hogy ha
X
⊆
A
és
Y
⊆
B
, akkor
vagy ezzel ekvivalens alakban
Mivel az egyenlőtlenség szimmetrikus
X
,
Y
-ban feltehetjük, hogy
X
≥
Y
. Továbbá
és így elég belátni azt, hogy
Itt
és így (9) következne abból, hogy
Ha
Y
≤
n
−
2
d
, akkor
Y
+
2
d
−
n
≤
0
, tehát
Ha
n
−
2
d
≤
Y
≤
X
≤
n
−
d
és
X
≥
d
, akkor
X
+
d
−
n
≤
0
, amiből
Ha
n
−
2
d
≤
Y
és
n
−
d
≤
X
, akkor figyelembe véve azt is, hogy
d
≤
n
∕
2
, kapjuk, hogy
Végül ha
X
≤
d
, felhasználjuk, hogy
és így elég azt megmutatni, hogy
ami magától értetődő, mert
Y
≤
X
≤
d
≤
n
2
.
- 19. feladat F Ö
A feladatnak az ötlettárban adott átfogalmazása
könnyen igazolható (vö. 4.21).
Tegyük fel, hogy
G
-ben nincsen 1-faktor, akkor 7.4b
miatt van olyan
X
⊆
A
=
{
u
1
,
…
,
u
n
}
, melyre
Γ
(
X
)
<
X
. Legyen mondjuk
X
=
{
u
1
,
…
,
u
k
}
és
B
−
Γ
(
X
)
=
{
v
1
,
…
,
v
l
}
. Így
k
+
l
>
n
, és
a
i
j
=
0
1
≤
i
≤
k
,
1
≤
j
≤
l
-re. Most
mert
A
duplán sztochasztikus, így
Másrészről
ami ellentmond annak, hogy
k
+
l
>
n
.
- 20. feladat F Ö
(a) Egyértelmű az ötlettár észrevételéből.
(b) Tegyük fel, hogy
G
-ben nincsen 1-faktor. Ekkor
det
(
a
i
j
)
=
0
. Alkosson mondjuk az első
k
+
1
oszlop minimális lineárisan összefüggő
oszloprendszert. Mivel az ezen
k
+
1
oszlop által alkotott
A
′
mátrix rangja
k
, tartalmaznia kell egy
k
×
k
nem-szinguláris almátrixot.
Feltehetjük, hogy ez első
k
sor és oszlop alkotja ezt az
almátrixot.
Mivel az első
k
+
1
oszlop lineárisan összefüggő, léteznek
olyan
λ
1
,
…
,
λ
k
+
1
számok, melyekre
Mivel
k
minimalitása miatt
λ
μ
≠
0
, tetszőleges
λ
μ
-vel leoszthatunk, és meghatározhatjuk
a
λ
ν
∕
λ
μ
számokat a Cramer szabály szerint az
első
k
sorból. Tehát minden
λ
ν
∕
λ
μ
hányados az
{
a
i
j
:
1
≤
i
≤
k
,
1
≤
j
≤
k
+
1
}
által generált testben van.
Azt állítjuk, hogy
a
i
j
=
0
, ha
k
+
1
≤
i
≤
n
és
1
≤
j
≤
k
+
1
. Megmutatjuk pl. azt, hogy
a
k
+
1
,
1
=
0
. (10)-ből tudjuk, hogy
Itt a jobb oldal az
{
a
i
j
;
(
i
,
j
)
≠
(
k
+
1
,
1
)
}
által generált altérben van. Az
a
i
j
-k algebrai függetlensége miatt ez
csak akkor lehetséges, ha
a
k
+
1
,
1
=
0
.
X
=
{
a
k
+
1
,
…
,
a
n
}
választással azt kapjuk, hogy
amivel bizonyítottuk 7.4b nem-triviális
felét [J. Edmonds,
J. Res. Natl. B. Standards 71B
(1967), 241–245].
- 21. feladat F Ö
Ha az
y
-ra tett kikötések lineárisan
függetlenek, a válasz természetesen
m
−
n
, ahol
n
=
V
(
G
)
; ha közülük
n
−
1
lineárisan független, de az
n
-edik nem, a dimenzió
m
−
n
+
1
. Azt állítjuk, hogy az első eset
következik be, ha
G
nem páros, és a második, ha
G
páros.
Ennek bizonyításához tekintsünk a (
∗
) kikötések bal oldalai között egy
nem-triviális lineáris relációt. Azt akarjuk
megmutatni, hogy ez csak akkor állhat fenn, ha
G
páros, és hogy ebben az esetben ez a
reláció szükségszerűen egyértelmű. Tehát legyen
azonosan 0, azaz
λ
v
+
λ
u
=
0
minden
(
u
,
v
)
élre. Felhasználva
G
összefüggőségét, arra a
következtetésre jutunk, hogy
λ
v
=
const
=
λ
, és olyan pontok, melyekre
λ
v
=
λ
, csak olyan pontokkal vannak
összekötve, melyekre
λ
v
=
−
λ
, és viszont. Tehát
G
páros. Mivel egy összefüggő gráf
2-színezése egyértelmű, azt is láthatjuk, hogy a (
∗
) kikötések bal oldalai közt fennálló
lineáris reláció egy skaláris szorzó erejéig
egyértelmű. Tehát páros gráf esetében van egy
egyértelmű
reláció, ahol
{
A
,
B
}
a
G
2-színezése [H. Saks,
Wiss. Z. TH. Ilmenau
12 (1966),
7–12].
- 22. feladat F Ö
Az ötlettárnak megfelelően legyen
(
x
,
y
)
∈
F
. Ha legalább 3 él köti
{
x
,
y
}
-t
{
u
,
v
}
-hez, akkor közülük kettő független,
pl.
(
x
,
u
)
és
(
y
,
v
)
. Így
F
=
{
(
x
,
y
)
}
∪
{
(
x
,
u
)
,
(
y
,
v
)
}
egy
F
-nél nagyobb párosítás, ami
ellentmondás. Tehát
F
minden éle
{
u
,
v
}
-hez legfeljebb két éllel csatlakozik.
Mivel
u
és
v
nincsenek sem egymással, sem
F
által le nem fedett ponttal összekötve
(különben
F
nem lenne maximális), ebből az
következik, hogy
Ez azonban ellentmondásban van azzal a
feltevéssel, hogy
d
(
u
)
is és
d
(
v
)
is legalább
n
(vö. a 10.19 feladattal is).
- 23. feladat F Ö
Legyen
X
az
F
0
által lefedett pontok halmaza. Az
ötletet követve legyen
F
a
G
egy olyan legnagyobb párosítása, mely
F
0
-ból a lehető legtöbb élt tartalmazza.
Azt állítjuk, hogy
F
lefedi
X
-et. Indirekte tegyük fel, hogy
létezik egy
F
által le nem fedett
x
∈
X
. Legyen
(
x
,
y
)
az
F
0
azon éle, mely
x
-szel szomszédos. Mivel
F
∪
{
(
x
,
y
)
}
nem párosítás
F
maximalitása miatt, létezik egy
y
-hoz illeszkedő
e
∈
F
él. Legyen
F
′
=
F
−
{
e
}
∪
{
(
x
,
y
)
}
, ekkor
F
′
egy
F
-fel azonos méretű párosítás, azaz
szintén egy legnagyobb párosítás. Továbbá több éle
közös
F
0
-lal, mint
F
-nek, ami ellentmondás.
- 24. feladat F Ö
(a) A
k
=
1
esetben egyetlen él eleget tesz a
feltételeknek. Tegyük fel, hogy
G
k
−
1
egyetlen 1-faktort tartalmazó gráf,
melyben minden fokszám legalább
k
−
1
. Legyen
G
k
−
1
′
egy másik, tőle diszjunkt példány, és
vegyünk még két új pontot,
x
-et és
y
-t. Kössük össze
x
-et
G
k
−
1
minden pontjával,
y
pedig
G
k
−
1
′
minden pontjával, végül
x
-et
y
-nal. Legyen
G
k
az így kapott gráf (55. ábra).
V
(
G
k
−
1
)
∪
V
(
G
k
−
1
′
)
minden pontjának fokszáma nagyobb mint
G
k
−
1
-ben vagy
G
k
−
1
′
-ben, így minden fokszáma legalább
k
. Ez nyilvánvalóan igaz
x
és
y
esetében is. Továbbá
G
k
-ban egyetlenegy 1-faktor van. Hiszen
legyen
F
a
G
k
tetszőleges 1-faktora.
Paritás-megfontolások miatt ennek tartalmaznia kell az
(
x
,
y
)
elvágóélt. Ekkor viszont a maradék egy
G
k
−
1
-beli és egy
G
k
−
1
′
-beli 1-faktort alkot. Mivel ezek
egyértelműek,
F
is egyértelműen meg van határozva.
Tehát
G
k
-ban legfeljebb egy 1-faktor van. De a
leírt 1-faktor (mely a
G
k
−
1
-beli,
G
k
−
1
′
-beli 1-faktorokból és az
(
x
,
y
)
-élből áll) valóban a
G
k
1-faktora. Tehát
G
k
-ban egyetlenegy 1-faktor van.
(b) Első megoldás. Tegyük fel, hogy
G
egy minimális ellenpélda. Legyen
F
az (egyetlen) 1-faktor, és legyen
e
1
∈
E
(
G
)
−
F
. Tekintsük a 6.27-ben meghatározott,
e
1
-et tartalmazó ekvivalencia-osztályt.
Ha ez csak
e
1
-ből áll, akkor
G
−
e
1
2-szeresen élösszefüggő, és
ellentmondásba kerültünk
G
minimalitásával. Tegyük fel, hogy az
ekvivalencia-osztály tartalmazza még az
e
2
,
…
,
e
k
,
k
≥
2
éleket is.
Legyen
G
1
a
G
−
{
e
1
,
…
,
e
k
}
tetszőleges komponense. 6.27 szerint
az
{
e
1
,
…
,
e
k
}
élek közül pontosan kettővel
szomszédos. Ha ez a két él nem
F
-beli, akkor indukcióval azt kapjuk,
hogy
G
1
-ben két különböző 1-faktor van,
melyek
F
−
E
(
G
1
)
-gyel együtt két különböző
G
-beli 1-faktort adnak. Tehát az
{
e
1
,
…
,
e
k
}
élek közül legalább egy olyan, mely
G
1
-hez illeszkedik,
F
-ben van. Mivel ez a
G
−
{
e
1
,
…
,
e
k
}
minden komponensére igaz, az
{
e
1
,
…
,
e
k
}
éleknek legalább a fele
F
-beli. Minthogy ez tetszőleges
ekvivalencia-osztályra igaz,
G
éleinek legalább a fele
F
-beli. Így
E
(
G
)
≤
V
(
G
)
. Mivel a
G
2-szeresen élösszefüggő, ez csak akkor
lehetséges, ha
G
egy kör. Viszont egy (páros) körben
két 1-faktor van.
Második megoldás. Tegyük fel, hogy a
G
2-szeresen élösszefüggő. Legyen
F
a
G
1-faktora. Legyen
C
olyan kör, melyre tetszőleges
F
-beli él vagy
C
-re esik, vagy teljesen diszjunkt
C
-től. Ilyen kör 6.30 szerint létezik.
C
-nek
F
-re nézve alternálónak kell lennie
(mivel az
F
egy 1-faktor). Tehát
C
-n alternálva (azaz
E
(
C
)
∩
F
éleit
E
(
C
)
−
F
éleivel helyettesítve) egy másik
1-faktort kapunk [A. Kotzig, Mat. Fyz. Časopis 9 (1959)
73–91; L. Beineke–M. D. Plummer, J. Comb. Th. 2 (1967)
285–289].
(c) A bizonyítás
E
(
G
)
szerinti indukcióval történik. (b)-nek
az ötlettárban megfogalmazott élesítése (b)-ből
triviálisan következik. Elég ezt összefüggő gráfokra
bizonyítani, mivel ha
G
-ben egyetlenegy 1-faktor van, akkor a
komponenseiben is. Duplázzuk meg
G
minden nem
F
-beli élét. Ezzel nem kaphatunk új
1-faktort, tehát a kapott
G
′
gráfban (b) miatt van elvágóél. Ennek
az élnek
F
-be kell tartoznia, mivel nem
dupláztuk meg.
Legyen
e
=
(
x
,
y
)
a
G
egy elvágó-éle, mely az (egyetlen)
F
1-faktorhoz tartozik, ekkor (
G
−
x
−
y
)-ban egyetlenegy 1-faktor van. Az
indukciós feltevés szerint
E
(
G
−
x
−
y
)
≤
(
n
−
1
)
2
. Minthogy
(
x
,
y
)
elvágóél, egyetlen pont sem lehet
összekötve
x
-szel is és
y
-nal is. Így legfeljebb
1
+
(
2
n
−
2
)
=
2
n
−
1
él szomszédos
x
és
y
egyikével. Tehát
Az eredmény éles, amint azt az 56. ábrához
hasonló struktúrájú gráfok mutatják. [G. Hetyei, Pécsi
Tan. Főisk. Közl. (1964) 151–168.]
- 25. feladat F Ö
Legyen
x
1
,
…
,
x
δ
egy legnagyobb
F
párosítás által le nem fedett pontok,
δ
=
δ
(
G
)
=
V
(
G
)
−
2
ν
(
G
)
. Legyen
F
=
{
e
1
,
…
,
e
ν
}
, és
f
i
az
x
i
-hez illeszkedő él (
i
=
1
,
…
,
δ
). Ekkor minden
f
i
x
i
-t egy
F
által lefedett ponthoz köti. Továbbá
nincs két olyan
f
i
, melyek ugyanazon
e
j
két végpontjához illeszkednek, mivel
ezáltal
F
növelhető lenne. Ennélfogva
kiválaszthatjuk az
e
j
egyik
u
j
végpontját (
j
=
1
,
…
,
ν
) úgy, hogy
{
u
1
,
…
,
u
ν
}
lefogja az összes
f
1
,
…
,
f
δ
élt. Mivel
d
(
u
j
)
≤
d
, ezért
és így
- 26. feladat F Ö
Követve az ötletet észrevehetjük, hogy ha
x
és
y
szomszédosak, akkor
ν
(
G
−
x
−
y
)
<
ν
(
G
)
, mert
G
−
x
−
y
bármely párosítása kiterjeszthető
(
x
,
y
)
-t felhasználva.
Legyen
x
,
y
két pont, melyek távolsága
k
>
1
, és legyen
z
egy minimális
(
x
,
y
)
-út tetszőleges belső pontja.
Indirekte tegyük fel, hogy
ν
(
G
−
x
−
y
)
=
ν
(
G
)
. Legyen
F
tetszőleges legnagyobb párosítás (
G
−
x
−
y
)-ban. Tekintsünk még egy
F
0
legnagyobb párosítást
G
−
z
-ben; ekkor
F
=
F
0
=
ν
(
G
)
(a rövidség kedvért
ν
). Vegyük észre, hogy
(a)
F
le kell, hogy fedje
z
-t, mert ellenkező esetben egy
ν
-elemű
G
−
x
−
z
-beli párosítás lenne, ami ellentmond
az indukciós feltevésnek, hogy
ν
(
G
−
x
−
z
)
<
ν
, és
(b) hasonlóan
F
0
-nak le kell fednie
x
-et és
y
-t.
F
∪
F
0
diszjunkt alternáló utak, körök és
közös
F
,
F
0
-élek uniója. Létezik egy
x
-ből induló
P
1
alternáló út és egy
y
-ból induló alternáló
P
2
út. Ha
P
1
=
P
2
, akkor helyettesítsük
F
∩
E
(
P
1
)
éleit
F
0
∩
E
(
P
1
)
éleivel
F
-ben; így egy
(
ν
+
1
)
-elemű párosítást kapunk (mivel
P
1
mindkét végén lévő él
F
0
-ba tartozik), ami ellentmondás. Így
P
1
≠
P
2
.
P
1
és
P
2
legalább egyike nem tartalmazza
z
-t, legyen mondjuk
z
∉
V
(
P
1
)
. Helyettesítsük
F
0
∩
E
(
P
1
)
éleit
F
∩
E
(
P
1
)
éleivel
F
0
-ban. A kapott
F
′
párosításra
F
′
≥
F
(mert
P
1
x
-ből egy
F
0
-beli élen indul, így ha
P
1
utolsó éle is
F
0
-ba tartozik, akkor
F
′
>
F
, különben
F
′
=
F
). Továbbá
z
-t még mindig nem fedi le
F
′
(mivel
z
∉
V
(
P
1
)
), tehát
F
′
egy legalább
ν
számosságú párosítás (
G
−
y
−
z
)-ben, ami megint ellentmondás.
Tehát
ν
(
G
−
x
−
y
)
<
ν
(
G
)
minden
x
,
y
-ra. Legyen
F
a
G
tetszőleges legnagyobb párosítása.
Ekkor legfeljebb egy
F
által le nem fedett pont van, mert ha
lenne két ilyen pont,
x
és
y
, akkor azt kapnánk, hogy
ez pedig ellentmondás. Továbbá
F
nem lehet 1-faktor, mert ha az lenne,
akkor
ami az egyik feltevésnek ellentmond. Így
ami az állítást bizonyítja [T. Gallai,
MTA Mat. Kut. Int. Közl.
8 (1963)
135–139].
- 27. feladat F Ö
(a) Legyen
X
⊆
V
(
G
)
és
F
a
G
egy legnagyobb párosítása. Legyenek
G
1
,
…
,
G
k
a
G
−
X
páratlan komponensei. Legyenek mondjuk
G
1
,
…
,
G
i
azok, melyek tartalmaznak
F
által le nem fedett pontot. Minden
G
j
-ből,
i
<
j
≤
k
, kell, hogy legyen
X
-be menő
F
-beli él paritási okokból. Mivel ezen
éleknek
X
különböző pontjaiba kell menniük,
ezért
Másrészről
G
1
,
…
,
G
i
mindegyike tartalmaz le nem fedett
pontot, így
Most már csak azt kell megmutatni – és ez a
bizonyítás nehéz pontja –, hogy létezik olyan
X
halmaz, melyre (11) egyenlőséggel
teljesül. Ezt
V
(
G
)
-re alkalmazott indukcióval fogjuk
belátni.
Először tegyük fel, hogy létezik egy
x
∈
V
(
G
)
, melyre
ν
(
G
−
x
)
<
ν
(
G
)
. Nyilvánvaló, hogy
ν
(
G
−
x
)
=
ν
(
G
)
−
1
, és így
Tehát az indukciós feltevés miatt létezik
egy
X
′
⊆
V
(
G
−
x
)
, melyre
Legyen
X
=
X
′
∪
{
x
}
. Ekkor
Másodszor tegyük fel, hogy
ν
(
G
−
x
)
=
ν
(
G
)
minden
x
∈
V
(
G
)
-re. Legyen
G
1
,
…
,
G
k
a
G
komponensei és
x
∈
V
(
G
i
)
. Ekkor
így
ν
(
G
i
−
x
)
=
ν
(
G
i
)
. Az előző feladat miatt ebből az
következik, hogy
V
(
G
i
)
páratlan és
δ
(
G
i
)
=
1
. Tehát
és
X
=
∅
eleget tesz a követelménynek [C.
Berge].
(b)
G
-ben akkor és csak akkor van 1-faktor,
ha
δ
(
G
)
=
0
, azaz (a) miatt akkor és csak akkor,
ha
Mivel
c
1
(
G
)
−
∅
≥
0
, a maximum mindig
≥
0
, és így (12) ekvivalens azzal, hogy
minden
X
⊆
V
(
G
)
esetén, mint azt állítottuk [W. T.
Tutte].
- 28. feladat F Ö
(a) Legyen
V
1
a
G
azon pontjainak halmaza, melyek minden
más ponttal össze vannak kötve, és melyre
V
1
=
V
(
G
)
−
V
1
. Azt akarjuk belátni, hogy ha
a
,
b
,
c
∈
V
2
, és
b
mind
a
-val, mind
c
-vel szomszédos, akkor
a
és
c
szomszédosak.
Tegyük fel, hogy ez nem áll fenn. Mivel
b
∈
V
2
, létezik egy negyedik pont,
d
, mely nem szomszédos
b
-vel. A
G
-re vonatkozó maximalitás-feltevés
miatt
G
+
(
a
,
c
)
-ben van egy
F
1
1-faktor és
G
+
(
b
,
d
)
-ben van egy
F
2
1-faktor. Nyilvánvaló, hogy
(
a
,
c
)
∈
F
1
,
(
b
,
d
)
∈
F
2
,
(
b
,
d
)
∉
F
1
és
(
a
,
c
)
∉
F
2
.
Tekintsük
F
1
∪
F
2
-t. Ez diszjunkt alternáló körökből és
F
1
és
F
2
közös éleiből áll.
(
a
,
c
)
rajta van egy
C
1
alternáló körön és hasonlóan
(
b
,
d
)
is rajta van egy
C
2
alternáló körön.
1. eset:
C
1
≠
C
2
. Ekkor cseréljük ki
E
(
C
1
)
∩
F
1
éleit
E
(
C
1
)
∩
F
2
éleivel
F
1
-ben, így egy
G
-beli 1-faktort kapunk, ami
ellentmondás.
2. eset:
C
1
=
C
2
.
b
-ből
(
b
,
d
)
-n indulva sétáljunk
C
1
-en; előbb-utóbb el kell érnünk
(
a
,
c
)
-t. Az általánosság megsértése nélkül
feltehetjük, hogy
a
-t
c
előtt érjük el.
Így van egy
(
b
,
a
)
-utunk, mely az
F
2
-beli
(
b
,
d
)
-élen indul és egy másik
F
2
-éllel végződik, mivel
(
a
,
c
)
∈
F
1
. Tehát
K
=
P
+
(
a
,
b
)
egy
F
2
-re nézve alternáló kör.
E
(
K
)
∩
F
2
éleit lecserélve
E
(
K
)
−
F
2
éleire a
G
egy 1-faktorát kapjuk
F
2
-ből. Ez pedig ismét
ellentmondás.
Tehát megmutattuk, hogy a szomszédosság egy
ekvivalencia-reláció
V
2
-n, azaz
V
2
diszjunkt teljes gráfokra esik
szét.
(b) Csak 7.27b nem-triviális részét bizonyítjuk:
ha
G
nem tartalmaz 1-faktort, akkor létezik
egy
X
⊆
V
(
G
)
, melyre
Ha
V
(
G
)
páratlan, akkor
X
=
∅
rendelkezik ezzel a tulajdonsággal.
Így feltehetjük, hogy
V
(
G
)
páros. Adjunk
G
-hez éleket addig, amíg nem hozunk
létre 1-faktort. Amikor ez már nem lehetséges,
ugyanazon a ponthalmazon lesz egy
G
′
gráfunk, mely rendelkezik azzal a
tulajdonsággal, hogy nem tartalmaz 1-faktort, de
bármely két nem szomszédos pontját összekötve már
1-faktort tartalmazó gráfot kapnánk.
(a) szerint
G
′
a következő alakú: ha
V
1
azon pontok halmaza, mely minden más
ponttal össze van kötve, akkor
G
′
−
V
1
a
G
1
,
…
,
G
k
diszjunkt teljes részgráfokból
áll.
Azt állítjuk, hogy legalább
V
1
+
1
páratlan teljes gráf van a
G
1
,
…
,
G
k
gráfok között. Tegyük fel, hogy ez
nincs így. Válasszuk ki minden páros
G
i
egy-egy 1-faktorát. Válasszunk egy-egy
maximális párosítást minden páratlan
G
i
-ből, ezzel pontosan egy pontot
hagytunk ki mindegyikből. Válasszunk független éleket,
melyek ezeket a kimaradt pontokat
V
1
-beli pontokkal párosítják össze.
Mivel
V
(
G
)
páros,
V
1
-ben páros számú le nem fedett pont
marad. De ezeket tetszőlegesen összepárosíthatjuk
egymással, mert
V
1
nyilvánvalóan a
G
′
egy teljes részgráfját feszíti ki.
Tehát egy 1-faktort kaptunk, és így
ellentmondást.
Tehát
G
′
−
V
1
-ben legalább
V
1
+
1
páratlan komponens van. Amikor
E
(
G
′
)
−
E
(
G
)
éleit eltávolítottuk, ezek a páratlan
komponensek széteshetnek, de mindegyik legalább egy (
G
−
V
1
)-beli páratlan komponenst eredményez.
Így
azaz
X
=
V
1
megfelelő választás lesz.
Megjegyzés: Az olvasó könnyen ellenőrizheti azt a
tényt (amit itt nem használtunk fel), hogy
G
1
,
…
,
G
k
mind páratlan és
k
=
V
1
+
2
[G. Hetyei, Pécsi Tanárképző
Főiskola Közl. 1974; L. Lovász,
J. Comb. Th.
19 (1975) 269–271].
- 29. feladat F Ö
(a) Tutte tétele szerint azt kell belátnunk, hogy
minden
X
⊆
V
(
G
)
-re.
Legyen
G
1
a
G
−
X
tetszőleges páratlan komponense. Mivel
G
2-szeresen összefüggő, legalább 2 él
köti
G
1
-et
X
-hez. Azonban nem lehet pontosan két
ilyen él, mert ebből az következne, hogy
G
1
fokszámainak összege
3
V
(
G
1
)
−
2
, páratlan szám, ami lehetetlen. Így
legalább 3 él köti
G
1
-et
X
-hez. Tehát legalább
3
c
1
(
G
−
X
)
él jön
G
−
X
páratlan komponenseiből
X
-be. De
X
minden pontja ezek közül legfeljebb
3-mal szomszédos, így a számuk legfeljebb
3
X
. Tehát
mint azt megköveteltük.
(Vegyük észre, hogy
G
-nek csak a 2-szeres élösszefüggőségét
használtuk fel. Viszont triviálisan látszik, hogy ha
egy 3-reguláris gráf 2-szeresen élösszefüggő, akkor
2-szeresen összefüggő is.) [J. Petersen]
(b) Ha
e
egy 3-reguláris gráf elvágóéle, akkor
e
-t minden 1-faktor tartalmazza (ha
ilyen egyáltalán van), mert
G
−
e
mindkét komponense páratlan (pontosan
egy páros fokszámú pontot tartalmaznak). Ennélfogva
elég egy egyszerű 3-reguláris gráfot konstruálni három
egy pontban találkozó elvágóéllel: egy ilyen gráf
bármely 1-faktorának mindhármat tartalmaznia kell, ami
lehetetlen. Az 57. ábra példa ilyen konstrukcióra (az
olvasóra bízzuk annak ellenőrzését, hogy ez-e a
legkisebb példa).
- 30. feladat F Ö
Tutte tétele szerint (7.27b), csak azt kell
megmutatnunk, hogy
bármely
X
⊆
V
(
G
)
-re. Tegyük fel, hogy ez nem áll fenn
valamely
X
-re. Mivel
V
(
G
)
páros, és így
ezért
Legyenek
G
1
,
…
,
G
m
a páratlan komponensek, és
G
m
+
1
,
…
,
G
M
a páros komponensek
G
′
−
X
-ben.
1
≤
i
≤
M
-re legyen
α
i
(ill.
β
i
) azon
E
(
G
)
−
E
(
G
′
)
-beli élek száma, melyek
G
i
-t
X
-hez kötik (ill. más
G
j
-hez), és jelölje
γ
i
azon
G
′
-beli élek számát, melyek
G
i
-t
X
-hez kötik. Ekkor
α
i
+
β
i
+
γ
i
G
összes
G
i
-t elhagyó éleinek száma, ami legalább
k
−
1
.
Továbbá, ha
G
i
páratlan komponens, akkor
α
i
+
β
i
+
γ
i
>
k
−
1
; hiszen
α
i
+
β
i
+
γ
i
=
k
−
1
azt jelentené, hogy a
G
gráf
V
(
G
i
)
által feszített részgráfjában a
fokszámok összege
V
(
G
i
)
−
k
+
1
=
k
(
V
(
G
i
)
−
1
)
+
1
≡
1
(
mod
2
)
. Így
Azon elhagyott élek száma, melyek
G
1
,
…
,
G
M
és
X
közül kötöttek össze kettőt,
∑
1
M
α
i
+
1
2
∑
1
M
β
i
, és ezért
Az
X
-be érkező összes élek száma
∑
1
M
α
i
+
∑
1
M
γ
i
, ami miatt
Az utolsó két egyenlőtlenséget összeadva
kapjuk, hogy
Összevetve ezt a (14) egyenlőtlenséggel, azt
látjuk, hogy
vagy, ami ezzel ekvivalens
ami ellentmond (13)-nek [J. Plesnik,
Mat. Čas. Slov. Akad. Vied.
22
(1972), 310–318].
- 31. feladat F Ö
Legyen
F
egy maximális párosítás, mely egy
adott
x
pontot kihagy. Legyen
y
egy
x
-szel szomszédos pont és legyen
F
0
a
G
−
y
1-faktora.
F
∪
F
0
diszjunkt alternáló utakból, közös
F
,
F
0
-beli élekből és egy
P
alternáló
(
x
,
y
)
-útból áll. Ekkor
P
0
=
P
+
(
x
,
y
)
olyan páratlan kör, mely
1
2
(
V
(
P
0
)
−
1
)
darab
F
-beli élt tartalmaz.
Tegyük fel, hogy
P
0
,
…
,
P
i
-t úgy választottuk, hogy minden
j
<
i
-re
P
j
+
1
egy páratlan
(
P
0
∪
…
∪
P
j
,
P
0
∪
…
∪
P
j
)
-út vagy egy páratlan kör, melynek
pontosan egy közös pontja van
P
0
∪
…
∪
P
j
-vel és
P
j
+
1
F
-re vonatkozóan alternál (
F
-beli éllel kezdődve és végződve; ha
P
j
+
1
páratlan kör, akkor tekintsük kezdő és
végpontjának a
P
0
∪
…
∪
P
j
-vel közös pontját). Tegyük fel, hogy
P
0
∪
…
∪
P
i
≠
G
. Legyen
(
a
,
b
)
tetszőleges nem
P
0
∪
…
∪
P
i
-beli él, melyre
a
∈
V
(
P
0
∪
…
∪
P
i
)
(ilyen él létezik, hiszen
G
összefüggő).
Ha
b
∈
V
(
P
0
∪
…
∪
P
i
)
, akkor vehetjük
P
i
+
1
=
(
a
,
b
)
-t. Tegyük fel, hogy
b
∉
V
(
P
0
∪
…
∪
P
i
)
. Legyen
F
i
a
G
−
b
1-faktora.
F
∪
F
i
diszjunkt alternáló körökből, közös
F
és
F
i
-beli élekből, valamint egy
Q
alternáló
(
b
,
x
)
-útból áll. Haladjunk
Q
-n
b
-ből
P
0
∪
…
∪
P
i
első
c
pontjába. Az utolsó él, melyen
átmentünk,
F
i
-be tartozik, mert minden
P
0
∪
…
∪
P
i
-t érintő
F
-él ebbe az unióba tartozik a
konstrukció szerint. Legyen
Q
′
a
Q
út
b
és
c
közötti darabja, és
P
i
+
1
=
Q
′
+
(
a
,
b
)
. Ekkor
P
i
+
1
eleget tesz a követelményeknek (58.
ábra).
Tehát ha
P
0
∪
…
∪
P
i
≠
G
, akkor tudunk választani egy
P
i
+
1
-t. Előbb vagy utóbb kimerítjük
G
-t, így megkapjuk a keresett
felbontást. [L. Lovász, Studia
Sci. Math. Hung. 7
(1972), 279–280;
vö. az Edmonds párosítási algoritmussal is,
7.34].
- 32. feladat F Ö
(a) Legyen
A
=
A
G
,
C
=
C
G
, …;
A
′
=
A
G
−
x
,
C
′
=
C
G
−
x
, … Elég azt belátni, hogy
D
′
=
D
, mivel ekkor
C
a
D
=
D
′
-vel nem szomszédos pontok halmaza,
tehát azonos
C
′
-vel.
Vegyük észre, hogy mivel
G
−
x
nem tartalmazza
G
egyetlen maximális párosítását sem,
ν
(
G
−
x
)
=
ν
(
G
)
−
1
. Így ha
M
a
G
tetszőleges maximális párosítása,
akkor
M
−
x
a
G
−
x
egy maximális párosítása. Mivel minden
y
∈
D
-re van egy
y
-t kihagyó maximális párosítás
G
-ben, és ez a
G
−
x
egy ugyanilyen maximális párosításához
vezet, következik, hogy
y
∈
D
′
, vagyis
D
⊆
D
′
.
Megfordítva, legyen
y
∉
D
, és indirekte tegyük fel, hogy
y
∈
D
′
. Ekkor létezik olyan
G
−
x
-beli maximális
M
′
párosítás, mely
y
-t kihagyja. Legyen
M
a
G
egy olyan maximális párosítása, mely
kihagyja az
x
egy
z
∈
D
szomszédját. Nézzük
M
∪
M
′
-t. Mivel
y
-t lefedi
M
, de
M
′
nem,
M
∪
M
′
y
-t tartalmazó komponense egy
y
-ból
M
-beli élen induló
P
út.
P
nem végződhet
M
′
-beli éllel, mert akkor
M
∩
E
(
P
)
éleit kicserélve
M
′
∩
E
(
P
)
éleire a
G
egy
y
-t kihagyó maximális párosítását
kapnánk. Tehát
P
az
M
egy élével végződik. Cseréljük ki
M
′
éleit
P
-n
M
∩
E
(
P
)
éleire. Ily módon egy
M
′
-nél nagyobb párosítást kapunk.
Ennélfogva ez az új párosítás nem lehet
G
−
x
-beli. Ebből az következik, hogy
P
x
-ben végződik. De most
(
M
−
E
(
P
)
)
∪
(
E
(
P
)
∩
M
′
)
∪
{
(
x
,
z
)
}
egy
y
-t kihagyó maximális párosítás, ami
megint csak ellentmondásra vezet.
(b) Legyenek
G
1
…
,
G
t
a
G
−
A
azon komponensei, melyeket
D
tartalmaz. Mivel egyetlen él sem köti
D
-t
C
-hez, ezek a komponensek
particionálják
D
-t. Legyen
H
a
C
által feszített részgráf.
Ha
A
pontjait egyenként elhagyjuk, (a)-ból
következik, hogy a
C
és
D
halmazok nem változnak. Tehát
G
−
A
minden maximális párosítása le fogja
fedni
H
összes pontját, de
D
minden pontjához lesz olyan
G
−
A
-bel maximális párosítás, mely azt nem
fedi le. Így
G
−
A
maximális párosításai egy
H
-beli
M
0
1-faktorból és minden
i
=
1
,
…
,
t
-re egy-egy
G
i
-beli
M
i
maximális párosításból állnak.
Továbbá, mivel minden
G
i
-beli pontot kihagy valamely
G
i
-beli maximális párosítás, minden
G
i
faktor-kritikus 7.26-szerint.
(c) Ha
M
a
G
tetszőleges maximális párosítása,
akkor a bizonyítás elején szereplő érvelés szerint
M
−
A
a
G
−
A
egy maximális párosítása. A (b)
részben már láttuk, hogy
M
−
A
-nak hogyan kell kinéznie.
(d) (b)-ből
A fenti
A
pontjainak egyenkénti elhagyására
vonatkozó megjegyzés szerint
Ebből az egyenlőség következik.
(e) Tegyük fel, hogy
c
1
(
G
−
X
)
≥
X
minden
X
-re fennáll. Konkrétan
c
1
(
G
−
A
)
≥
A
. Másrészről
c
1
(
G
−
A
)
=
t
. Így (d)-ből
azaz
G
-ben van 1-faktor. Ez bizonyítja Tutte
tételének nem-triviális irányát. [T. Gallai,
MTA Mat. Kut. Int. Közl.
8 (1963), 373–395;
J. Edmonds, Canad. J. Math.
17 (1965), 449–467.]
(f) Lásd 59. ábra.
- 33. feladat F Ö
I. Tegyük fel, hogy
M
′
nem maximális párosítás
G
′
-ben. Ekkor
G
′
-ben van olyan
M
0
párosítás, melyre
M
0
>
M
′
.
M
0
a
G
olyan párosítása, mely legfeljebb egy
pontot tartalmaz
C
-ből. Így
C
-ből hozzávehetünk
k
élt
M
0
-hoz úgy, hogy egy olyan
M
1
párosítást kapjunk, melyre
ez pedig ellentmondás.
II. Most tegyük fel, hogy
M
′
a
G
′
egy maximális párosítása. Tekintsük a
D
′
,
A
′
,
C
′
halmazokat
G
′
-re definiálva, mint 7.32-ben. Legyen
c
a
C
képe
G
′
-ben. Mivel
M
′
kihagyja
c
-t,
c
∈
D
′
. Tehát ha „felfújjuk”
c
-t, a
G
′
−
A
′
c
-t tartalmazó komponense a
G
−
A
′
C
-t tartalmazó komponensévé válik, mely
szintén páratlan. Így
és
mutatva, hogy
M
maximális párosítás
G
-ben.
- 34. feladat F Ö
(a) I. Egy (
∗
)–(
∗
∗
) tulajdonságokkal rendelkező erdő
mindenképpen létezik; pl. legyen az erdő ponthalmaza az
M
által le nem fedett pontok halmaza,
élhalmaza pedig legyen üres. Legyen
F
egy maximális (nem bővíthető) ilyen
erdő. Ekkor egyetlen külső pont sem lehet szomszédos
V
(
G
)
−
V
(
F
)
-fel, hiszen
F
tulajdonságai miatt
(
G
−
V
(
F
)
)
∩
M
a
G
−
V
(
F
)
1-faktora (mivel minden lefedetlen
pontnak
F
-beli gyökérnek kell lenni) és így ha
a
∈
V
(
G
)
−
V
(
F
)
szomszédos a
b
F
-beli külső ponttal és
(
a
,
c
)
∈
M
, akkor
(
a
,
b
)
-t és
(
a
,
c
)
-t hozzávehetnénk
F
-hez.
II. Ha
F
két különböző komponensének egy-egy
külső pontja, mondjuk
x
és
y
szomszédos, akkor tekintsük a
P
és
Q
,
x
-et és
y
-t az
F
-beli komponensük gyökerével összekötő
utakat. Ekkor
R
=
P
∪
Q
∪
{
(
a
,
y
)
}
egy
M
-re nézve alternáló út, és ha
kicseréljük
M
∩
E
(
R
)
-t
E
(
R
)
−
M
-re, akkor egy
M
-nél nagyobb párosítást kapunk (60.
ábra).
III. Most tegyük fel, hogy
F
azonos komponensének két külső pontja,
u
és
v
szomszédos. Ezek
F
bizonyos éleivel együtt egy páratlan
C
kört alkotnak. Legyen
w
a
C
azon pontja, mely legközelebb van
F
ezen komponensének
r
gyökeréhez (
w
=
r
előfordulhat). A
w
-t
r
-hez kötő alternáló úton „váltva” egy
olyan új
M
0
párosítást kapunk, mely
1
2
(
V
(
C
)
−
1
)
C
-beli élt tartalmaz, és
M
0
többi éle nem érinti
C
-t. Az előző eredmény felhasználásával
ha összehúzzuk
C
-t,
M
0
′
=
M
0
−
E
(
C
)
akkor és csak akkor lesz maximális
párosítás a kapott
G
′
gráfban, ha
M
0
(vagy ekvivalensen
M
) a
G
egy maximális párosítása. Továbbá ha
G
′
-ben találunk egy
M
0
′
-nél nagyobb párosítást, akkor könnyen
kiterjeszthetjük a
G
egy
M
-nél nagyobb párosításává.
IV. Végül tegyük fel, hogy
G
külső pontjai függetlenek. Legyen
A
a belső pontok halmaza. Ekkor a külső
pontok (
G
−
A
)-ban izoláltak lesznek; a számuk
Mivel
A
=
M
∩
E
(
F
)
, következik, hogy
7.27 miatt a jobb oldal felső korlát
ν
(
G
)
-re. Tehát
M
maximális párosítás.
A keresett algoritmus most már könnyen adódik a
fenti eredmények összegzésével. Minden lépésben van egy
G
-beli
M
párosítás és egy
F
⊂
G
erdő, mely kielégíti (
∗
)-ot és (
∗
∗
)-ot. Megvizsgáljuk az
F
külső pontjaival szomszédos
éleket.
1
∘
Ha van egy
F
-beli külső pontot
V
(
G
)
−
V
(
F
)
-beli ponthoz kötő él, akkor
F
-et megnöveljük az I. rész
szerint.
2
∘
Ha van olyan él, mely
F
két különböző komponensének külső
pontját köti össze, akkor
M
-et megnöveljük a II. rész
szerint.
3
∘
Ha van olyan él, mely
F
két azonos komponensének külső pontját
köti össze, akkor összehúzunk egy páratlan kört a III.
rész szerint és megpróbáljuk növelni a kapott gráf
kapott párosítását. Vagy levonhatjuk a következtetést,
hogy
M
maximális (nem bővíthető), vagy
növelhetjük
M
-et.
4
∘
Ha minden külső pontra illeszkedő él
azt belső ponthoz köti, akkor levonhatjuk a
következtetést, hogy
M
maximális párosítás.
Megjegyzések. 1. A fenti algoritmus hatékony
abban az értelemben, hogy
O
(
n
4
)
, vagyis polinomiális számú lépés
alatt lefut. Valójában jelöljük
f
(
n
)
-nel azt a legkisebb felső korlátot,
ahány lépés alatt az algoritmus eldönti, hogy egy
n
pontú gráf egy adott
M
párosítása maximális-e és helyettesíti
egy nagyobbal, ha nem az.
O
(
n
2
)
lépés alatt talál egy (
∗
) és (
∗
∗
) tulajdonságoknak eleget tevő
maximális (nem bővíthető) erdőt. (Bizonyos külső pontok
listáját fenntartjuk. Minden lépésben megvizsgáljuk,
hogy a lista első pontja szomszédos-e nem
F
-beli ponttal. Ha igen, megnöveljük
F
-et és az új külső pontot a lista
végéra tesszük. Ha nem, kihúzzuk ezt a külső pontot a
listáról. Egy ilyen lépéshez
O
(
n
)
szomszédosság-vizsgálat szükséges.
Minden lépésben vagy
V
(
F
)
, vagy a kihúzott külső pontok száma
nő, így a lépések száma
O
(
n
)
.) Ez után végre kell hajtani a
2
∘
,
3
∘
,
4
∘
lépések egyikét. Mivel ehhez a
legrosszabb esetben, amikor
3
∘
-t kell végrehajtanunk, legfeljebb
f
(
n
−
2
)
+
O
(
n
2
)
lépés szükséges, azt kapjuk, hogy
ami miatt
f
(
n
)
=
O
(
n
3
)
. Mivel a párosítás méretét legfeljebb
O
(
n
)
-szer növeltük meg, a teljes
algoritmus lefut nem több, mint
O
(
n
4
)
lépésben.
2. A következő megjegyzés nagyon fontos: ha a
3
∘
lépést hajtjuk végre, az
F
erdőt egy azonos típusú erdőre
képezzük le, és ezt már nem kell újra számolni. Ennek
felhasználásával
O
(
n
3
)
-ra javíthatjuk az algoritmus hosszára
adott felső korlátot. Ugyanezen észrevétel és az
algoritmus gondosabb vizsgálata mellett elkerülhetnénk
7.33 (és ezen keresztül a Gallai–Edmonds struktúra
tétel) felhasználását. Azt is megjegyezzük, hogy az
A
G
,
C
G
,
D
G
halmazok meghatározhatók és számos
korábbi eredmény is (pl. 7.26, 7.27, 7.31, 7.32)
levezethető az algoritmusból. Az olvasó érdekesnek és
tanulságosnak találhatja a részletek
kidolgozását.
(b) Lásd 61. ábra (vö. 7.32f) [J. Edmonds,
Canad. J. Math.
17 (1965), 449–467].
- 35. feladat F Ö
Tegyük fel, hogy
G
-ben nincsen 1-faktor. Tekintsük az
A
,
C
,
D
halmazokat, mint 7.32-ben. Legyen
G
1
,
…
,
G
t
a
G
[
D
]
komponensei, ekkor 7.32 szerint ezek
faktor-kritikusak. 7.31-ből az következik (bár
közvetlenül is könnyen belátható), hogy ha
V
(
G
i
)
>
1
, akkor
G
i
tartalmaz páratlan kört. Így a
G
1
,
…
,
G
t
legfeljebb egyikében van egynél több
pont. Legyen mondjuk
Pontosan
k
él köti
G
i
-t
A
-hoz
i
=
2
,
…
,
t
-re. Mivel
A
minden pontja ezek közül legfeljebb
k
-val szomszédos, azt kapjuk, hogy
vagy ezzel ekvivalensen
t
≤
A
+
1
. Mivel
ebből az következik, hogy
ami miatt
G
-ben van 1-faktor, ez pedig
ellentmondás. [D. R. Fulkerson,
A. J. Hoffman, M. H. McAndrew,
Canad. J. Math. 17 (1965) 166–177].
- 36. feladat F Ö
(a) Legyen
x
az ötletnek megfelelő pont, és
(
x
,
y
)
tetszőleges
x
-hez illeszkedő él.
y
-t mindenképpen lefedi
F
valamely
e
éle, különben
F
+
(
x
,
y
)
egy nagyobb párosítás lenne. Most
F
−
e
+
(
x
,
y
)
maximális
(
x
,
y
)
-t tartalmazó párosítás.
(b) Indukciót alkalmazunk
E
(
G
)
-re. 7.24b miatt tudjuk, hogy
G
-ben két különböző 1-faktor van,
F
1
és
F
2
. Legyen
C
egy
F
1
∪
F
2
-beli kör. Ha a
C
valamely pontja másodfokú, akkor
készen vagyunk, mivel ekkor a rá illeszkedő két él
rendre az
F
1
, illetve
F
2
1-faktorba tartozik.
Így tegyük fel, hogy
C
minden pontjának fokszáma legalább 3.
Azt állítjuk, hogy
G
−
e
2-szeresen összefüggő valamely
e
∈
E
(
C
)
-re. Ez el fogja dönteni a kérdést;
hiszen (
G
−
e
)-ben van 1-faktor (
e
az
F
1
és
F
2
közül pontosan egybe tartozik) és így
az indukciós hipotézis miatt van egy
x
pont, melyre
G
−
e
minden
x
-szel szomszédos éle
G
−
e
valamely 1-faktorába tartozik. Mivel
e
-t tartalmazza egy 1-faktor,
x
ugyanezen tulajdonsággal fog
rendelkezni
G
-ben.
Indirekte tegyük fel, hogy (
G
−
e
)-nek van egy
x
e
elvágópontja minden
e
∈
E
(
C
)
-re. Természetes, hogy
x
e
∈
V
(
C
)
. Válasszuk
e
-t úgy, hogy
x
e
e
-hez
C
-n a lehető legközelebb legyen.
Nyilvánvaló, hogy
x
e
nem lehet
e
végpontja.
Legyen
f
a
C
azon éle, mely
e
-hez csatlakozik a
C
kör rövidebbik
(
e
,
x
e
)
-ívén (62. ábra). Ekkor
e
választása miatt,
x
f
-nek a másik
(
e
,
x
e
)
-íven kell lennie. Ekkor az
e
és
f
közös pontja,
y
, szomszédos egy harmadik
(
y
,
z
)
éllel. Mivel
G
−
y
összefüggő,
z
egy
P
úttal kapcsolódik
C
−
y
valamely pontjához. Most már látjuk,
hogy akármelyik pontban éri is el
P
a
C
-t, ellentmondásba kerülünk azzal a
ténnyel, hogy mind
{
e
,
x
e
}
, mind
{
f
,
x
f
}
lefogja
G
-t. [J. Zaks, Combin. Structures Appl.
Gordon and Breach (1970) 481–488.]
- 37. feladat F Ö
I. Legyen
w
tetszőleges 2-párosítás és válasszunk
egy független
X
⊆
V
(
G
)
halmaz. Legyen
Az
X
-ből
Γ
(
X
)
-be haladó élek összes
w
-súlya
másrészről legföljebb
2
Γ
(
X
)
, ami miatt
Tehát
Ez bizonyítja, hogy a 2-párosítások
maximális mérete legföljebb
II. Először megjegyezzük, hogy
Valóban, tetszőleges
X
⊆
V
(
G
)
-re definiáljuk
X
′
=
X
−
Γ
(
X
)
-et. Ekkor
X
′
független és
Γ
(
X
′
)
⊆
Γ
(
X
)
−
X
. Így
mutatva, hogy
X
−
Γ
(
X
)
maximuma valamely
X
független halmazon éretik el.
Legyen
G
0
az ötlet szerint definiált páros gráf.
Vegyük észre, hogy
X
⊆
V
(
G
)
-re
Γ
G
0
(
X
)
=
Γ
(
X
)
. Ennélfogva
7.5 szerint
G
0
-ban van egy
V
(
G
)
−
δ
független élből álló
F
halmaz. Minden
e
=
(
u
,
v
)
∈
E
(
G
)
-re jelölje
w
0
(
e
)
azt, hogy
F
hány élt tartalmaz
(
v
′
,
u
′
)
és
(
u
′
,
v
′
)
közül; így
w
0
(
e
)
=
0
1 vagy 2. Továbbá bármely rögzített
v
-re legfeljebb egy
F
-beli él hagyja el
v
-t és legfeljebb egy másik hagyja el
v
′
-t. Tehát
azaz
w
0
egy 2-párosítás. Továbbá
amiből
[vö. W. T. Tutte,
Proc. Amer. Math. Soc.
4 (1953),
922–931].
- 38. feladat F Ö
I. Vegyük észre, hogy egy
V
(
G
)
méretű 2-párosítás szükségszerűen
maximális. Ennélfogva ha
G
-ben van egy
F
1-faktor, akkor
F
éleit 2 súllyal véve egy olyan
maximális 2-párosítást kapunk, mely az
F
maximális 1-párosítást
tartalmazza.
II. Legyen
G
faktor-kritikus és tegyük fel, hogy
V
(
G
)
>
1
. Legyen
F
tetszőleges
G
-beli maximális párosítás. 7.31
megoldása mutatja, hogy létezik egy
P
0
páratlan kör, mely
F
-ből
1
2
(
V
(
P
0
)
−
1
)
élt tartalmaz, és melyre
F
−
E
(
P
0
)
a
G
−
V
(
P
0
)
gráf 1-faktora. Legyen
ekkor
w
egy
V
(
G
)
méretű,
F
-et tartalmazó 2-párosítás.
III. Tegyük fel, hogy
G
nem faktor-kritikus és nincs benne
1-faktor. Tekintsük a
G
Gallai–Edmonds felbontását (7.32).
Legyenek
G
1
,
…
,
G
t
a
G
[
D
G
]
komponensei; legyen mondjuk
Ugyanúgy, mint előbb, legyen
Mivel így
minden
X
⊆
Y
-ra fennáll, 7.5-öt az
Y
-nal szomszédos élek alkotta páros
gráfra alkalmazva azt kapjuk, hogy
Y
−
δ
=
k
−
δ
független él köti
Y
-t
Γ
(
Y
)
⊆
A
-hoz. Feltehetjük, hogy
y
1
,
…
,
y
k
−
δ
összepárosítható az
A
halmaz
k
−
δ
darab pontjával.
7.23 szerint létezik a
G
-nek egy maximális
F
párosítása, mely lefedi
y
1
,
…
,
y
k
−
δ
-t. Definiáljunk egy
w
F
-et tartalmazó maximális 2-párosítást
a következőképpen: legyen
G
k
+
1
,
…
,
G
m
összekötve
A
-val
F
valamely éleivel (
m
≤
t
). 7.32 miatt
F
∩
E
(
G
i
)
egy maximális párosítás
G
i
-ben (
i
=
m
+
1
,
…
,
t
), és így a bizonyítás II. részéhez
hasonlóan definiálhatunk
G
i
-n egy
V
(
G
i
)
méretű
w
i
2-párosítást, mely tartalmazza
F
∩
E
(
G
i
)
-t valamely
i
=
m
+
1
,
…
,
t
-re. Minden
e
∈
E
(
G
)
-re legyen
Ekkor nyilvánvaló, hogy
w
egy
F
-et tartalmazó 2-párosítás. Azt kell
megmutatnunk, hogy
w
maximális (nem bővíthető). Vegyük
észre, hogy a
w
-nek pontosa két éle tartalmaz minden
pontot
y
k
−
δ
+
1
,
…
,
y
k
kivételével, mely pontokat
w
egyetlen éle sem tartalmazza. Tehát
Ez 7.37 szerint azt mutatja, hogy
w
maximális 2-párosítás.
- 39. feladat F Ö
Legyen
L
a
G
egy Euler-vonala. Tekintsük
L
minden második élét. Mivel az élek
teljes száma páros, ez lehetséges. Ekkor ezen élek egy
d
-faktort alkotnak.
- 40. feladat F Ö
Legyen
G
→
a
G
egy pszeudoszimmetrikus irányítása
(lásd 5.13), legyen
V
(
G
)
=
{
v
1
,
…
,
v
n
}
, és definiáljuk a következő
G
0
páros gráfot:
Vegyük észre, hogy
G
0
egy
d
-reguláris páros gráf és
G
előáll
G
0
-ból minden
1
≤
i
≤
n
-re
v
i
és
v
i
′
azonosításával.
Színezzük a
G
0
éleit
d
színnel úgy, hogy minden szín egy
1-faktort alkosson (ez 7.10 miatt lehetséges).
v
i
és
v
i
′
azonosításával ez a
G
éleinek egy
d
-színezését adja, melyben minden szín
egy 2-faktort alkot. (Figyeljük meg a különbséget ez és
a 7.37 bizonyításában szereplő konstrukció között; ott
a páros gráf két élét
G
ugyanazon élére képeztük le,
ennélfogva csak azt a következtetést vonhattuk le, hogy
a páros gráf egy párosítása a gráf egy 2-párosításához
vezet; itt nincs két él, melyeket azonos élre képeztünk
le, így a páros gráf egy 1-faktora a gráf egy
2-faktorához vezet.)
- 41. feladat F Ö
Először tegyük fel, hogy minden fokszám páros. Ha
az élek száma páros, akkor ugyanazzal a bizonyítással,
mint 7.39-ben, megkapjuk a keresett részgráfot (azaz
tekintsünk egy Euler-vonalat és vegyük minden második
élét). Másrészről ha létezik ilyen
F
részgráf, akkor
ami miatt
E
(
G
)
páros.
Tegyük fel, hogy vannak páratlan fokszámú pontok.
Legyen
v
egy új pont, és kössük össze
v
-t
G
minden páratlan fokszámú pontjával.
v
-nél még szükség esetén egy hurkot is
felvéve, egy olyan
G
′
gráfot konstruáltunk, melyen már
minden fokszám és az élek száma is páros. Így tehát
ismét 7.39 szerint
G
′
-ben van egy
F
′
feszítő részgráf, melynek fokszámaira
Legyen
F
=
F
′
−
v
. Ekkor bármely
x
∈
V
(
G
)
-re,
Így minden összefüggő gráf rendelkezik ezzel
a tulajdonsággal, a páratlan élszámú Euler-gráfok
kivételével.
- 42. feladat F Ö
(a) Ha egy gráfban minden pont foka páratlan,
akkor a gráfnak páros sok pontja van. Így
G
-ben páros sok pontnak kell
lenni.
Megfordítva tegyük fel, hogy
V
(
G
)
páros, mondjuk
V
(
G
)
=
{
x
1
,
…
,
x
2
m
}
. Legyen
P
i
egy
x
i
-et
x
i
+
m
-hez kapcsoló út (
i
=
1
,
…
,
m
), és legyen
Minden
x
∈
V
(
G
)
-re
és így
F
a kívánt tulajdonsággal rendelkező
feszítő részgráf.
(b) Legyen
x
∈
V
(
G
)
,
d
G
(
x
)
≥
4
. Vegyünk a
G
két
(
x
,
y
)
,
(
x
,
z
)
élét, melyekre
G
−
(
x
,
y
)
−
(
x
,
z
)
összefüggő. (Ilyen két él létezik,
hiszen legyen
y
,
z
a
G
−
x
két különböző komponensében, ha
G
−
x
nem összefüggő. Ekkor
G
−
(
x
,
y
)
−
(
x
,
z
)
összefüggő, ha
G
−
x
összefüggő, mert
d
G
(
x
)
≥
3
és akkor is, ha
G
−
x
nem összefüggő, mivel
G
−
x
minden komponense legalább két éllel
kapcsolódik
x
-hez.) Vegyünk egy új
x
′
pontot és kössük össze
x
,
y
és
z
-vel. Az
(
x
,
x
′
)
él összehúzásával visszakapjuk
G
-t.
A fenti eljárás ismétlésével véges sok lépés után
egy 3-reguláris
G
′
gráfot kapunk, hiszen a
összeg minden lépésben csökken.
G
a
G
′
összehúzásával áll elő és
G
′
2-szeresen élösszefüggő (és így a
7.29a-ban szereplő megjegyzésnek megfelelően 2-szeresen
összefüggő).
Így
G
′
7.29a szerint tartalmaz egy
F
1-faktort. Ekkor
F
′
=
E
(
G
′
)
−
F
egy 2-faktor. Az új éleke
összehúzásával megkapjuk
G
′
-ből
G
′
-t, és
F
′
-t a
G
egy pozitív fokszámú részgráfjára
képeztük le.
- 43. feladat F Ö
(a) Helyettesítsünk minden
x
pontot egy
f
(
x
)
független pontból álló
M
x
halmazzal. Ha
(
x
,
y
)
∈
E
(
G
)
, akkor
M
x
minden pontja össze van kötve
M
y
minden pontjával, különben nem kötné
egyetlen él sem
M
x
-et
M
y
-hoz. könnyen ellenőrizhető, hogy a
kapott gráfban akkor és csak akkor van 1-faktor, ha
G
-ben van
f
-párosítás.
(b) Osszunk fel minden élt két ponttal, és
definiáljuk az új pontokon
f
(
x
)
-et
1
-nek. Ekkor a kapott
G
0
gráfban akkor és csak akkor van
f
-faktor, ha
G
-ben van
f
-faktor.
G
0
minden élének legalább egyik
x
végpontjára
f
(
x
)
=
1
; ennélfogva
G
0
-ban akkor és csak akkor van
f
-faktor, ha van
f
-párosítása. Ha kicserélünk minden
G
0
-beli
x
pontot
f
(
x
)
független pontra ugyanúgy, mint
(a)-ban, akkor egy olyan
G
′
gráfot kapunk, melybe akkor és csak
akkor van 1-faktor, ha
G
-ben van
f
-factor [W. T. Tutte,
Canad. J. Math.
6 (1954), 347–352].
- 44. feladat F Ö
Legyen
G
→
′
az ötlet szerint definiált irányított
gráf; azaz legyen
V
′
=
{
x
′
:
x
∈
V
(
G
)
}
,
V
″
=
{
x
″
:
x
∈
V
(
G
)
}
,
V
(
G
→
′
)
=
V
′
∪
V
″
és
E
(
G
→
′
)
=
{
(
x
′
,
y
″
)
:
(
x
,
y
)
∈
E
(
G
)
}
. Legyen
G
′
az irányítás figyelmen kívül
hagyásával előálló gráf. Definiáljuk
h
(
y
)
-t a következőképpen:
Nyilvánvaló, hogy
G
-ben akkor és csak akkor van a
keresett faktor, ha
G
′
-ben van
h
-faktor. 7.16 szerint ez akkor és csak
akkor van így, ha
és minden
X
⊆
V
′
,
Y
⊆
V
″
-re
Más szóval akkor és csak akkor, ha
és minden
X
,
Y
⊆
V
(
G
)
-re
ahol
m
G
(
X
,
Z
)
az
X
-ben kezdődő és
Z
-ben végződő élek számát
jelöli.
- 45. feladat F Ö
Az ötletet követve legyen
G
1
a
G
éleinek felosztásával kapott gráf és
terjesszük ki
f
-et
V
(
G
1
)
-re az előírás szerint. Vegyük észre,
hogy
G
-nek akkor és csak akkor van a kívánt
tulajdonságú irányítása, ha
G
1
-ben van
f
-faktor.
G
1
nyilvánvalóan páros a
V
(
G
)
és
V
(
G
1
)
−
V
(
G
)
szín-osztályokkal. Tehát 7.16 szerint
G
1
-ben akkor és csak akkor van 1
f
-faktor, ha
és minden
X
⊆
V
(
G
)
,
Y
⊆
E
(
G
)
esetén az
X
és
Y
közötti illeszkedések száma nem
kevesebb mint
Nyilvánvalóan elég ezt arra a speciális
esetre megkövetelni, amikor
X
és
Y
között nincsen illeszkedés, de
Y
az összes
X
-hez nem illeszkedő élt tartalmazza.
Ekkor (16) azt mondja, hogy
(
∗
) legalább
∑
x
∈
X
f
(
x
)
él szomszédos
X
-szel minden
X
⊆
V
(
G
)
-re.
(15) és (
∗
) szükséges és elégséges feltétele
annak, hogy
G
a kérdéses módon irányítható
legyen.
- 46. feladat F Ö
(a) Indukciót alkalmazunk a pontok számára.
Először tegyük fel, hogy
G
egy kör,
V
(
G
)
=
{
x
1
,
…
,
x
n
}
és
E
(
G
)
=
{
(
x
1
,
x
2
)
,
…
,
(
x
n
,
x
1
)
}
. Ha
g
(
x
)
>
0
minden
x
i
∈
V
(
G
)
-re, vehetjük
F
=
(
V
(
G
)
,
∅
)
-t. Így tegyük fel, hogy pl.
g
(
x
1
)
=
0
. Ekkor tegyük
(
x
1
,
x
2
)
-t
F
-be. Az irányított kör mentén haladva
tegyük
(
x
i
,
x
i
+
1
)
-et
F
-be, ha
(
x
i
−
1
,
x
i
)
∈
F
és
g
(
x
i
)
=
1
, vagy
(
x
i
−
1
,
x
i
)
∉
F
és
g
(
x
i
)
=
0
. Ilyen módon döntve minden élről
végül 1 vagy 2
F
-él lesz
x
1
-nél, tehát
d
F
(
x
1
)
≠
g
(
x
1
)
=
0
. A többi pont eleget tesz a
követelménynek, mert
F
-et így konstruáltuk.
Tegyük fel, hogy
G
nem egyetlen kör. Ekkor találunk olyan
x
∈
V
(
G
)
pontot, melyre
G
1
=
G
−
x
összefüggő és tartalmaz kört.
Definiáljuk
g
1
-et
V
(
G
1
)
-n a következőképpen: ha
g
(
x
)
>
0
, legyen
g
1
=
g
; ha
g
(
x
)
=
0
, kiválasztjuk az
x
egy
y
szomszédját és legyen
Az indukciós feltevés szerint
g
1
-nek van olyan
F
1
feszítő részgráfja, melynek fokszámai
különböznek
G
1
fokszámaitól. A
g
(
x
)
>
0
esetben
F
=
F
1
a
G
egy keresett részgráfja. Ha
g
(
x
)
=
0
,
F
=
F
1
∪
{
(
x
,
y
)
}
rendelkezik a kívánt
tulajdonsággal.
(b) I. Tegyük fel, hogy mind (i), mind (ii)
fennáll; legyen
F
egy feszítő részgráf, melynek
fokszámai
≠
g
(
x
)
, és
G
→
egy irányítás
g
(
x
)
kifokokkal. Fordítsuk meg az
F
éleinek irányítását. Mivel a kapott
gráf irányított körmentes, van olyan
x
pontja, melynek befoka 0. Ismét
megfordítva
F
éleit
x
befoka
g
(
x
)
lesz, ami miatt
x
pontosan
g
(
x
)
F
-beli éllel szomszédos, ez viszont
ellentmondás.
II. Legyen
G
tetszőleges fa, megmutatjuk, hogy
ekkor vagy (i), vagy (ii) teljesül. Legyen
x
egy elsőfokú pont. Ha
g
(
x
)
<
0
vagy
g
(
x
)
>
1
, akkor (ii) teljesül. Hiszen vegyünk
fel
x
-ben egy hurkot, alkalmazzuk (a)-t,
majd ezután hagyjuk el a hurkot. Olyan feszítő
részgráfot kapunk, melyben minden
y
≠
x
pont fokszáma
≠
g
(
y
)
, és természetesen
x
fokszáma különbözik
g
(
x
)
-től.
Tehát feltehetjük, hogy
g
(
x
)
=
0
vagy
g
(
x
)
=
1
. Tegyük fel pl., hogy
g
(
x
)
=
1
(a másik eset hasonlóan adódik). Ha
G
−
x
-ben van egy
F
feszítő részgráf minden
y
∈
V
(
G
)
−
{
x
}
-nél
≠
g
(
y
)
fokszámokkal, ugyanezen részgráf (
x
-et mint izolált pontot tartalmazva)
eleget tesz a
G
-re vonatkozó követelményeknek; tehát
(b) megint igaz. Ennélfogva tegyük fel, hogy nem
létezik ilyen
F
. Ekkor az indukciós feltevés miatt
G
−
x
-nek van egy irányítása, melyben
minden
y
∈
V
(
G
)
−
x
befoka
g
(
y
)
. Irányítsuk az
x
-hez illeszkedő élt
x
felé. Ekkor a kapott irányítás
mutatja, hogy (i) fennáll [L. Lovász,
Periodica Math. Hung.
4 (1973), 121–123].
- 47. feladat F Ö
A szükségesség nyilvánvaló, minthogy minden
n
pontú fának
n
−
1
éle van. Tegyük fel, hogy
d
1
+
…
+
d
n
=
2
n
−
2
. Indukciót alkalmazunk
n
-re. Az
n
≤
2
eset triviális, így tegyük fel, hogy
n
≥
3
. Ekkor
d
1
=
1
, mivel
d
1
≥
2
azt jelentené, hogy
d
1
+
…
+
d
n
≥
2
n
>
2
n
−
2
. Az is igaz, hogy
d
n
>
1
, mert
d
n
=
1
-ből
d
1
+
…
+
d
n
=
n
<
2
n
−
2
következne. Mivel
létezik egy
T
fa
d
2
,
…
,
d
n
−
1
,
d
n
−
1
fokszámokkal. Vegyünk fel egy új
pontot és kössük össze
T
d
n
−
1
fokszámú pontjával; ekkor a kapott fa
a megkövetelt fokszámokkal rendelkezik.
- 48. feladat F Ö
A szükségesség ismét nyilvánvaló. Az
elégségességet
∑
i
=
1
n
d
i
-re alkalmazott indukcióval
bizonyítjuk. Két esetet különböztetünk meg.
I.
d
n
−
2
<
d
n
. Ekkor
d
n
−
1
egy legnagyobb elem
d
1
,
d
2
,
…
,
d
n
−
2
,
d
n
−
1
−
1
,
d
n
−
1
-ben, így azt kell belátnunk, hogy
és
mely állítások a feltételekből
nyilvánvalóak.
II.
d
n
−
2
=
d
n
. Ekkor
d
n
−
1
=
d
n
. Nyilvánvaló, hogy (17) fennáll és
feltéve, hogy
d
n
−
2
≥
2
. Ha
d
n
−
2
=
1
, akkor (19) bal oldala (1) miatt
páratlan, így triviálisan legalább 1.
Tehát
d
1
,
…
,
d
n
−
2
,
d
n
−
1
−
1
,
d
n
−
1
-re a feladat feltevése igaz, így
indukcióval létezik egy
n
pontú hurokmentes gráf, mely
megvalósítja ezt a sorozatot. A
d
n
−
1
−
1
és
d
n
−
1
fokszámú pontokat egy új éllel
összekötve olyan gráfot kapunk, melynek fokszámai
d
1
,
…
,
d
n
.
- 49. feladat F Ö
Legyen
K
az az egyszerű hurokmentes irányított
gráf, melyet
V
(
K
)
=
{
v
1
,
…
,
v
n
}
,
E
(
K
)
=
{
(
v
i
,
v
j
)
:
i
≠
j
}
definiál. A kívánt tulajdonságokkal
rendelkező irányított gráf létezésének kérdése
ekvivalens a
K
egy adott ki- és befokokkal rendelkező
részgráfja létezésének kérdésével. 7.44 miatt ez
ekvivalens (1) és (2)-vel, mivel
K
{
v
i
;
i
∈
I
}
-et
{
v
j
;
j
∉
J
}
-hez kötő éleinek a száma
I
(
n
−
J
)
−
I
−
J
. (Itt emlékezzünk arra, hogy
K
-ban nincsen hurok!)
Ha
f
1
≤
…
≤
f
n
és
g
1
≤
…
≤
g
n
, akkor minden
I
,
J
-re, melyekre
I
=
k
és
J
=
l
valamint
Így (2) helyettesíthető a következővel:
Mivel (20) természetesen a (2) egy speciális
esete (melyre
I
=
{
n
−
k
+
1
,
…
,
n
}
és
J
=
{
1
,
…
,
l
}
), így szükséges; továbbá mivel
láttuk, hogy (20)-ből (2) következik az
f
1
≤
…
≤
f
n
,
g
1
≤
…
≤
g
n
feltétel mellett.
- 50. feladat F Ö
Először tegyük fel, hogy létezik egy egyszerű
G
gráf
d
1
,
…
,
d
n
fokszámokkal és legyen
v
i
a
d
i
fokszámú pont. Legyen
p
=
n
−
d
n
. Azt állítjuk, hogy
G
választható úgy, hogy
v
n
szomszédos
v
1
,
…
,
v
n
−
1
mindegyikével (de más ponttal nem).
Válasszuk
G
-t az összes olyan gráf közül, melyre
d
G
(
v
i
)
=
d
i
úgy, hogy
v
n
{
v
p
,
…
,
v
n
−
1
}
közül a lehető legtöbb ponttal legyen
szomszédos. Tegyük fel, hogy
v
n
nem szomszédos
v
k
-val valamely
p
≤
k
≤
n
−
1
-re. Ekkor
v
n
szomszédos kell, hogy legyen valamely
v
ν
,
1
≤
ν
≤
p
−
1
-gyel, mivel
d
n
=
n
−
p
. Mivel
d
ν
≤
d
k
, van egy olyan
v
m
pont,
m
≠
k
,
ν
, mely
v
k
-val szomszédos, de
v
ν
-vel nem. Hagyjuk el a
(
v
k
,
v
m
)
és
(
v
ν
,
v
n
)
éleket, de vegyünk fel, egy
(
v
k
,
v
n
)
és
(
v
ν
,
v
m
)
élt. Így egy azonos fokszámokkal
rendelkező gráfot kapunk, melyben
v
n
több ponttal szomszédos
{
v
p
,
…
,
v
n
−
1
}
közül, mint
G
-ben, ez pedig ellentmondás.
Tehát van egy olyan
G
gráfunk
d
1
,
…
,
d
n
fokszámokkal, melyben
v
p
,
…
,
v
n
−
1
mindegyike szomszédos
v
n
-nel.
v
n
-t elhagyva egy
d
1
,
…
,
d
p
−
1
,
d
p
−
1
,
d
p
+
1
−
1
,
…
,
d
n
−
1
−
1
fokszámokkal rendelkező gráfot
kapunk.
Megfordítva tegyük fel, hogy a
d
k
′
számok egy egyszerű
G
′
gráf fokszámai. Ekkor
v
n
-t triviálisan felvehetjük [V. Havel,
Čas. Pest. Mat. 80 (1955) 477–480].
- 51. feladat F Ö
(a) Az ötletet követve válasszuk
H
-t az adott ki- és befokokkal
olyannak, a
H
-beli 2 hosszú irányított körök száma
maximális legyen. Jelölje
H
˜
azon
(
x
,
y
)
∈
E
(
H
)
-beli élek által alkotott gráf
részgráfot, melyre
(
y
,
x
)
∉
E
(
H
)
.
H
˜
nem tartalmaz páros hosszú irányított
kört. Hiszen tegyük fel, hogy
(
x
1
,
…
,
x
2
k
)
a
H
˜
egy páros irányított köre. Ekkor
hagyjuk el
(
x
2
,
x
3
)
,
…
,
(
x
2
k
,
x
1
)
-et; de vegyük fel
(
x
2
,
x
1
)
,
(
x
4
,
x
3
)
,
…
,
(
x
2
k
,
x
2
k
−
1
)
-et. Így olyan gráfot kapunk, melynek
ki- és befokai azonosak
H
ki- és befokaival, de több 2 hosszú
irányított kört tartalmaz.
Ugyanez az érvelés mutatja, hogy
H
˜
-ben nem lehet páros sok élt
tartalmazó zárt irányított vonal. Minthogy
H
˜
-ban a ki- és befokok egyenlőek, ezért
él-diszjunkt irányított körök uniója (vö. 5.6). A
fentiek miatt ezek páratlanok és bármely kettőt véve
nem lehet közös pontjuk, mert akkor páros sok élt
tartalmazó vonalat alkotnának.
Tegyük fel, hogy van két
C
1
,
C
2
irányított kör a
H
˜
fenti irányított
kör-dekompozíciójában,
C
1
=
(
x
0
,
…
,
x
2
k
)
és
C
2
=
(
y
0
,
…
,
y
2
l
)
. Ha
(
x
0
,
y
0
)
∈
E
(
H
)
, akkor
(
x
0
,
y
0
)
∉
E
(
H
˜
)
a fentiek miatt, és így
(
y
0
,
x
0
)
∈
E
(
H
)
és
C
1
∪
C
2
∪
{
(
x
0
,
y
0
)
,
(
y
0
,
x
0
)
}
egy páros számú élből álló vonal, ami
miatt ugyanúgy, mint fent ellentmondásra jutunk. Így
(
x
0
,
y
0
)
,
(
y
0
,
x
0
)
∉
E
(
H
)
. Hagyjuk el
(
x
0
,
x
1
)
,
(
x
2
,
x
3
)
,
…
,
(
x
2
k
,
x
0
)
,
(
y
0
,
y
1
)
,
(
y
2
,
y
3
)
,
…
,
(
y
2
l
,
y
0
)
-et, de vegyük fel
(
x
2
,
x
1
)
,
…
,
(
x
2
k
,
x
2
k
−
1
)
,
(
y
2
,
y
1
)
,
…
,
(
y
2
l
,
y
2
l
−
1
)
,
(
x
0
,
y
0
)
,
(
y
0
,
x
0
)
-et. Megint egy azonos fokszámú
egyszerű irányított gráfhoz jutunk, melyben több 2
hosszú irányított kör van.
Tehát
H
˜
legfeljebb 1 irányított kört
tartalmaz. Ha pontosan egyet tartalmaz, akkor ez
páratlan és
∑
i
=
1
n
d
i
=
E
(
H
)
páratlan, ami ellentmond a
feltevésnek. Tehát
H
˜
-nak nincsen éle; azaz
H
ellentétes élpárokból áll. Minden
ilyen élpárt egyetlen irányítatlan éllel helyettesítve,
egy
d
1
,
…
,
d
n
fokszámú egyszerű gráfot kapunk [vö.
D. R. Fulkerson, A. J. Hoffman,
M. H. McAndrew, Canad. J. Math.
17 (1965), 166–177].
(b) (a) miatt egy
d
1
,
…
,
d
n
fokszámokkal rendelkező egyszerű
irányítatlan gráf létezése ekvivalens egy olyan
egyszerű irányított
H
gráf létezésével a
{
v
1
,
…
,
v
n
}
pontokon, melyre
d
H
+
(
v
i
)
=
d
H
−
(
v
i
)
=
d
i
(
i
=
1
,
…
,
n
) (a mellett a szükséges feltevés
mellett, hogy
d
1
+
…
+
d
n
páros). 7.49 miatt ilyen irányított
gráf akkor és csak akkor létezik, ha minden
k
-ra
l
∈
{
1
,
…
,
n
}
,
Elég ezt a
k
+
l
≤
n
esetre megkövetelni. Valóban, ha
k
+
l
>
n
, akkor (21) ekvivalens a
következővel:
ami szintén levezethető (21)-ből
k
és
l
helyére rendre
n
−
l
-et és
n
−
k
-t írva.
Ha
k
+
l
≤
n
, akkor
Így ha
akkor (21) teljesül. Másrészről (23)
speciális esete (21)-nek, amennyiben
m
=
max
{
j
:
d
j
≤
k
}
-t és
l
=
min
{
n
−
k
,
m
}
-t veszünk. Így (23) szükséges és
elégséges feltétel [P. Erdős, T. Gallai].
- 52. feladat F Ö
Először tegyük fel, hogy
d
1
,
…
,
d
n
egy összefüggő gráf fokszámai. Ekkor
7.51-ből (1) következik, míg (2) és (3)
triviális.
Megfordítva tegyük fel, hogy
d
1
,
…
,
d
n
eleget tesz (1) (2)-nek és (3)-nak.
(1) miatt van egyszerű
G
gráf a
d
1
,
…
,
d
n
fokszámokkal. Válasszuk
G
-t úgy, hogy a lehető legkevesebb
komponense legyen.
Azt állítjuk, hogy
G
összefüggő. Tegyük fel, hogy nem,
ekkor (3) szerint komponenseinek egyike tartalmaz kört.
Legyen
G
1
az a komponens és
(
x
,
y
)
a
G
1
egy a körön lévő éle. Legyen
G
2
tetszőleges másik komponens és
(
u
,
v
)
a
G
2
egy éle (
G
2
-ben van él, hiszen (2) miatt nem
lehet izolált pont). Ekkor
G
−
{
(
x
,
y
)
,
(
u
,
v
)
}
+
{
(
x
,
u
)
,
(
y
,
v
)
}
egy gráf azonos halmazon, azonos
fokszámokkal és kevesebb komponenssel, ez viszont
ellentmondás. [P. Erdős, T. Gallai].
- 53. feladat F Ö
Legyen
G
egy gráf, benne
F
egy 1-faktor és
v
1
,
…
,
v
n
a pontjai, melyekre
d
(
v
i
)
=
d
i
. Ekkor nyilvánvaló, hogy
G
−
F
fokszám-sorozata
d
1
−
1
,
…
,
d
n
−
1
. A megfordítás bizonyításához legyen
G
tetszőleges egyszerű gráf a
V
=
{
v
1
,
…
,
v
n
}
ponthalmazon, és
d
G
(
v
i
)
=
d
i
. Legyen
G
′
egy másik egyszerű gráf
V
-n, melyre
d
G
′
(
v
i
)
=
d
i
−
1
. Válasszunk ki az összes ilyen
gráf-pár közül egy olyat, melyre
E
(
G
)
−
E
(
G
′
)
minimális. Azt állítjuk, hogy
G
′
⊆
G
. Tegyük fel, hogy nem, ekkor vannak
az
E
(
G
′
)
−
E
(
G
)
éleihez illeszkedő pontok. Legyen
x
ezek közül egy olyan, mely a legtöbb (
k
)
E
(
G
′
)
−
E
(
G
)
-beli élhez illeszkedik. Ekkor
x
-et
k
+
1
E
(
G
)
−
E
(
G
′
)
-beli él tartalmazza. Legyen
(
x
,
y
1
)
,
…
,
(
x
,
y
k
+
1
)
∈
E
(
G
)
−
E
(
G
′
)
és
(
x
,
z
)
∈
E
(
G
′
)
−
E
(
G
)
.
Mivel
d
G
(
z
)
>
d
G
′
(
z
)
, van egy olyan
v
pont, melyre
(
z
,
v
)
∈
E
(
G
)
−
E
(
G
′
)
. Válasszunk egy
1
≤
i
≤
k
+
1
-et, melyre
y
i
≠
v
. Ekkor
(
v
,
y
i
)
∈
E
(
G
)
. Mert ha
(
v
,
y
i
)
∉
E
(
G
)
, akkor
(
x
,
y
i
)
-t és
(
z
,
v
)
-t elhagyva
G
-ből, de hozzávéve
(
x
,
z
)
-t és
(
v
,
y
i
)
-t, olyan gráfot kapunk, melynek
fokszámai azonosak
G
fokszámaival, de több éle közös
G
′
-vel. Hasonlóan
(
v
,
y
i
)
∉
E
(
G
′
)
, mert ha
(
v
,
y
i
)
∈
E
(
G
′
)
, elhagyhatnánk
(
v
,
y
i
)
-t és
(
x
,
z
)
-t
G
′
-ből, de felvehetnénk
(
x
,
y
i
)
-t és
(
z
,
v
)
-t
G
′
-ben és így egy olyan gráfot kapnánk,
melynek fokszáma azonos
G
′
-vel, de több közös éle van
G
-vel. Így
(
v
,
y
i
)
∈
E
(
G
)
−
E
(
G
′
)
.
Ha
v
≠
y
1
,
…
,
y
k
+
1
, akkor
v
legalább
k
+
2
E
(
G
)
−
E
(
G
′
)
-beli éllel (
(
v
,
z
)
,
(
v
,
y
1
)
,
…
,
(
v
,
y
k
+
1
)
) szomszédos, tehát így a feltevés
miatt legalább
k
+
1
E
(
G
′
)
−
E
(
G
)
-beli éllel szomszédos, ami ellentmond
x
választásának. Ha mondjuk
v
=
y
1
, akkor megint csak legalább
k
+
2
E
(
G
)
−
E
(
G
′
)
-beli éllel szomszédos (ebben az
esetben ezek
(
v
,
z
)
,
(
v
,
x
)
,
(
v
,
y
2
)
,
…
,
(
v
,
y
k
+
1
)
), és ugyanúgy, mint előbb,
ellentmondásra jutunk. [S. Kundu, Discrete Math.
6
(1973), 367–376; L. Lovász, Periodica
Math. Hung. 5
(1974) 149–151].