Problem B. 5397. (May 2024)

B. 5397. Let \(\displaystyle G\) be a graph (possibly with multiple edges) with the following property: whenever the vertices of \(\displaystyle G\) are partitioned into \(\displaystyle t\) disjoint sets, there are at least \(\displaystyle 2t-2\) edges connecting different sets. Show that the edges of \(\displaystyle G\) can be colored red or blue such that the red edges and the blue edges each form a connected graph (and reaching all the vertices).

(Proposed by Kada Williams, Cambridge)

(6 pont)

Deadline expired on June 10, 2024.

Sorry, the solution is available only in Hungarian. Google translation

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.

Statistics:

7 students sent a solution.
3 points:	1 student.
2 points:	1 student.
1 point:	3 students.
0 point:	1 student.
Unfair, not evaluated:	1 solutions.

Problems in Mathematics of KöMaL, May 2024