A B. 5397. feladat (2024. május)

B. 5397. Egy gráfra (amely többszörös éleket is tartalmazhat) teljesül, hogy akárhogyan osztjuk szét a csúcsait $\displaystyle t$ darab diszjunkt halmazba, legalább $\displaystyle 2t-2$ él különböző halmazok között vezet. Bizonyítsuk be, hogy a gráf éleit ki lehet színezni pirosra vagy kékre úgy, hogy a kék és a piros élek is összefüggő (és minden csúcsot elérő) gráfot alkossanak.

Javasolta: Williams Kada (Cambridge, UK)

(6 pont)

A beküldési határidő 2024. június 10-én LEJÁRT.

Megoldás. A megoldás során élünk a következő elnevezésekkel:

• Egy gráf egy $\displaystyle t$-részes partíciójának nevezzük a csúcsainak $\displaystyle t$ db diszjunkt halmazba való szétosztását.
• Szingulárisnak nevezzük azt a partíciót, amelyben minden csúcs külön halmazba kerül.
• Ha egy $\displaystyle t$-részes partíció esetén (ahol $\displaystyle t \geq 2$) a gráf legalább $\displaystyle 2t-2$ éle különböző halmazok között vezet , akkor jó partícióról, egyébként rossz partícióról beszélünk.
• Azt mondjuk, hogy egy gráf teljesíti a partíciós feltételt, ha minden partíciója jó.
• A jó partíciók között fontos szerepet játszanak a feszes partíciók, ezeknél pontosan $\displaystyle 2t-2$ él megy különböző halmazok között. (Megjegyzés: az egyetlen halmazba való osztásnál persze $\displaystyle 2 \cdot 1 - 2 = 0$ él vezet különöző halmazok között, de ezt nem tekintjük feszes partíciónak.)
• Egy gráf jól színezhető, ha a gráf éleit ki lehet színezni pirosra vagy kékre úgy, hogy a kék és a piros élek is összefüggő és minden csúcsot elérő gráfot alkossanak (az ilyen színezést jó színezésnek nevezzük).

Indirekt bizonyítunk. Tegyük fel, hogy nem igaz a feladat állítása – azaz van olyan gráf, amely teljesíti a partíciós feltételt, de mégsem színezhető jól. Legyen $\displaystyle G$ a ,,legkisebb ellenpélda'', pontosabban az összes ellenpélda közül egy minimális csúcsszámú és az ilyen csúcsszámúak között egy minimális élszámú ellenpélda-gráf. Jelölje $\displaystyle G$ csúcsszámát $\displaystyle n$, élszámát $\displaystyle e$. Feltevésünk szerint tehát minden olyan $\displaystyle G'$ gráf esetén, amelynek $\displaystyle n' < n$ csúcsa van, vagy $\displaystyle n'=n$ csúcsa és $\displaystyle e' < e$ éle van, teljesül, hogy ha teljesíti a partíciós feltételt, akkor jól is színezhető.

(Feltehetjük, hogy $\displaystyle n \geq 3$, hiszen egy és két csúcsú gráfokra triviálisan teljesül a feladat állítása.)

Biztosak lehetünk benne, hogy $\displaystyle G$-ban van feszes partíció, hiszen különben $\displaystyle G$ bármelyik élét törölve egy ugyanannyi csúcsú, de eggyel kevesebb élű ellenpéldát kapnánk.

I. eset: $\displaystyle G$-nek van nem szinguláris feszes partíciója.

Legyen egy nem szinguláris feszes partíció $\displaystyle V = V_1 \cup V_2 \cup \ldots \cup V_t$ (itt értelemszerűen $\displaystyle V$ a $\displaystyle G$ csúcshalmaza, és $\displaystyle 2 \leq t \leq n-1$). Az általánosság korlátozása nélkül feltehetjük, hogy $\displaystyle |V_1| \geq 2$, jelölje $\displaystyle G_1$ a gráfnak a $\displaystyle V_1$ által feszített részgráfját.

Ekkor $\displaystyle G_1$ is teljesíti a partíciós feltételt. Ennek belátásához tekintsük $\displaystyle V_1$-nek egy tetszőleges $\displaystyle V_1 = W_1 \cup W_2 \cup \ldots \cup W_s$ partícióját. Mivel

$\displaystyle V = \underbrace{W_1 \cup W_2 \cup \ldots \cup W_s}_{V_1} \cup V_2 \cup V_3 \cup \ldots \cup V_t$

a $\displaystyle G$ gráf egy $\displaystyle (s+t-1)$-részes partíciója, tehát legalább $\displaystyle 2s+2t-4$ él vezet különböző halmazok között. Ezen élek közül pontosan $\displaystyle 2t-2$ darab vezet különböző $\displaystyle V_i$-k között (a feszes $\displaystyle V_1 \cup V_2 \cup \ldots \cup V_t$ partícióban különböző halmazok közt futó élek), tehát még legalább $\displaystyle 2s-2$ olyan élnek kell lennie, amelyek különböző $\displaystyle W_i$-k közt vezetnek. Ezzel beláttuk, hogy $\displaystyle G_1$ teljesíti a partíciós feltételt. Mivel $\displaystyle |V_1| < n$, ezért ebből következik, hogy $\displaystyle G_1$ jól színezhető is.

Másrészt tekintsük azt a $\displaystyle G^*_1$ gráfot is, amelyet úgy kapunk $\displaystyle G$-ből, hogy az összes $\displaystyle V_1$-beli csúcsot egyetlen $\displaystyle v^*_1$ csúccsá húzzuk össze (a $\displaystyle G^*_1$ csúcshalmaza tehát $\displaystyle V \setminus V_1 \cup \{ v^*_1 \}$; a két $\displaystyle V_1$-beli csúcsot összekötő élek törlődnek; a $\displaystyle v^*_1$ csúcs pedig annyi éllel van összekötve minden $\displaystyle w \in V \setminus V_1$ csúccsal, mint ahány él vezet $\displaystyle G$-ben a $\displaystyle w$-ből a $\displaystyle V_1$ halmazba; a $\displaystyle V_1$-et elkerülő élek pedig változatlanul megmaradnak $\displaystyle G^*_1$-ben is). Könnyen látható, hogy a $\displaystyle G^*_1$ gráf is teljesíti a partíciós feltételt (hiszen minden partíciója megfelel a $\displaystyle G$ egy partíciójának). Mivel $\displaystyle G^*_1$-nek $\displaystyle n$-nél kevesebb csúcsa van, ezért $\displaystyle G^*_1$ is jól színezhető.

Mivel $\displaystyle G$ minden éle vagy $\displaystyle G_1$-ben, vagy $\displaystyle G_1^*$-ban szerepel, ezért a $\displaystyle G_1$ és $\displaystyle G_1^*$ egy-egy jó színezése egyesíthető a $\displaystyle G$ egy színezésévé, amelyről könnyen látszik, hogy jó színezés (mindegyik szín összefüggő és minden csúcsot elér $\displaystyle G$-ben). Ez ellentmond $\displaystyle G$ ellenpélda voltának, tehát az alábbi, 2. esetnek kell fennálnia.

II. eset: $\displaystyle G$ egyetlen feszes partíciója a szinguláris partíció.

Mivel a szinguláris partícióban minden él különböző halmazok között vezet, ezért a $\displaystyle G$ gráfnak $\displaystyle 2n-2$ éle kell legyen. Tehát az átlagos fokszám $\displaystyle 4$ alatt van, így van legfeljebb 3-fokú csúcs, egy ilyen csúcsot nevezzünk $\displaystyle v_0$-nak. Ha $\displaystyle v_0$ foka legfeljebb 2 lenne, akkor a $\displaystyle V = \{v_0 \} \cup ( V \setminus \{ v_0 \})$ 2-részes partíció feszes (vagy rossz) lenne, ellentmondva a II. eset feltételeinek. Tehát $\displaystyle v^*$ foka pontosan 3.

Tekintsük most azt az $\displaystyle n-1$ csúcsú $\displaystyle G_0$ gráfot, amelyet úgy kapunk, hogy $\displaystyle G$-ből töröljük a $\displaystyle v_0$ csúcsot (az éleivel együtt), majd a maradék gráfban $\displaystyle v_0$ három egykori szomszédja (jelölje őket: $\displaystyle v_1$, $\displaystyle v_2$, $\displaystyle v_3$) közül kettőt ($\displaystyle v_1$-et és $\displaystyle v_2$-t) összekötünk egy fantom-éllel.

Belátjuk, hogy $\displaystyle G^*_0$ teljesíti a partíciós feltételt. A szinguláris partíció esetén minden él különböző csúcsok között megy, márpedig $\displaystyle G_0$-nak éppen $\displaystyle 2n-2 - 3 + 1 = 2(n-1)-2$ éle van.

Tekintsük most $\displaystyle G_0$ egy tetszőleges nem szinguláris $\displaystyle V \setminus \{ v_0 \} = V^*_1 \cup V^*_2 \cup \ldots \cup V^*_t$ partícióját. Ekkor persze

$\displaystyle \{ v_0 \} \cup V^*_1 \cup V^*_2 \cup \ldots \cup V^*_t$

a $\displaystyle G$ gráfnak egy nem szinguláris, tehát nem is feszes $\displaystyle (t+1)$-részes partíciója, azaz legalább $\displaystyle 2(t+1)-2+1 = 2t+1$ db él megy különböző halmazok között. Ezek közül csak a $\displaystyle v_0$-ból induló 3 él veszik el a $\displaystyle G_0^*$-ra való visszatérésnél, tehát legalább $\displaystyle 2t-2$ él megy különböző halmazok között a $\displaystyle G_0$ tetszőlegesen választott nem szinguláris $\displaystyle t$-részes partíciójánál.

Azt kaptuk, hogy $\displaystyle G^*_0$ is teljesíti a partíciós feltételt. Mivel $\displaystyle n-1$ csúcsú, ezért ebből következik, hogy jól színezhető is.

A $\displaystyle G^*_0$ egy tetszőleges jó színezését ki tudjuk egészíteni a $\displaystyle G$ egy jó színezésévé a következő módon: $\displaystyle v_0v_1$ és $\displaystyle v_0v_2$ élek színe egyezzen meg a $\displaystyle v_1v_2$ fantom-él színével, míg $\displaystyle v_0v_3$ él színe legyen ezzel ellentétes. Így mindkét szín eléri a $\displaystyle v_0$ csúcsot, és a színek összefüggősége is megmarad. Ezzel a II. eset is ellentmondással zárult, azaz a teljes indirekt bizonyításnak is a végére értünk.

Statisztika:

7 dolgozat érkezett.
3 pontot kapott:	1 versenyző.
2 pontot kapott:	1 versenyző.
1 pontot kapott:	3 versenyző.
0 pontot kapott:	1 versenyző.
Nem versenyszerű:	1 dolgozat.

A KöMaL 2024. májusi matematika feladatai