Internet Olympiad Problema 7

[Beniamin Bogosel]

Consideram \( K_7 \) graful complet cu 7 varfuri. Care este cel mai mic numar natural \( N \) pentru care exista o colorare a muchiilor grafului cu \( N \) culori astfel incat nu exista un ciclu monocolor.

Internet Olympiad, Ariel University, Samaria, Israel

[maxim bogdan]

Asta e un model pentru \( N=4. \)
Evident numarul de muchii dintr-un \( K_{7} \) este \( (^7_{2})=21. \)
Vom demonstra ca pentru \( N=3 \) nu avem solutie!

Din "Principiul Cutiei" va rezulta ca o culoare se foloseste de cel putin \( 7 \) ori (mai corect spus: exists o culoare care se foloseste de \( 8 \) ori sau fiecare culoare se foloseste de \( 7 \) ori).

Ramane sa aratam ca intr-un graf \( G=(V;E) \) cu \( |V|=7;\ |E|=7 \) avem un ciclu. Singura demonstratie care o am este analizand fiecare caz dupa
\( \Delta(G)=\max\{d(i)| i\in V\}. \) Evident \( 2\leq \Delta(G)\leq 6. \)

Daca \( \Delta(G)=2\Rightarrow 2\cdot 7\geq\sum_{i\in V}d(i)=2|E|=14. \)

Deci \( d(i)=d(j);\ i,j\in\{1,\dots,7\}\Rightarrow G \) este \( 2 \)-regulat.

Se va folosi urmatoarea lema: Orice graf \( G \) contine un drum (path) de lungime \( \delta(G) \) si un ciclu de lungime cel putin \( \delta(G)+1 \) (daca \( \delta(G)\geq 2 \)).

Pentru demonstratie vezi R. Diestel- Graph Theory (pag. 8 ).

Pentru \( \Delta(G)\in\{5;6\} \) se demonstreaza usor (deoarece avem un numar mic de cazuri de analizat), iar pentru \( \Delta(G)\in\{3;4\} \) sunt destul de multe cazuri si nu are rost sa le postez.

O sa ma gandesc la o alta solutie mai putin complicata!

[maxim bogdan]

Vrem sa demonstram ca in orice graf \( G=(V;E) \), cu \( |V|=7 \); \( |E|=7 \) exista un ciclu.

Se foloseste urmatoarea
Lema Daca \( G \) este un graf cu \( n \) varfuri in care nu exista un ciclu atunci \( |E|\leq n-1. \)

[Scorpius]

Vrem sa demonstram ca in orice graf \( G=(V;E) \), cu \( |V|=7 \); \( |E|=7 \) exista un ciclu.

Se foloseste urmatoarea
Lema Daca \( G \) este un graf cu \( n \) varfuri in care nu exista un ciclu atunci \( |E|\leq n-1. \)

Poti sa demonstrezi lema?

[Marius Mainea]

Vrem sa demonstram ca in orice graf \( G=(V;E) \), cu \( |V|=7 \); \( |E|=7 \) exista un ciclu.

Se foloseste urmatoarea
Lema Daca \( G \) este un graf cu \( n \) varfuri in care nu exista un ciclu atunci \( |E|\leq n-1. \)

Poti sa demonstrezi lema?

E foarte simplu, prin inductie dupa n.

Daca exista un varf din care nu pleaca nici o muchie, eliminam acel varf si aplicam pasul de inductie.

Altfel , exista un varf al grafului din care pleaca exact o muchie (demonstrati).

Eliminand acel varf obtinem un graf (G',E') cu |G'|=n-1 varfuri, care nu are cicluri deci \( |E^{\prime}|\le n-2 \) .

Aplicam ipoteza de inductie si gata.

[maxim bogdan]

Lema Daca \( G \) este un graf cu \( n \) varfuri in care nu exista un ciclu atunci \( |E|\leq n-1. \)

Solutie. Vom demonstra lema prin inductie dupa n. Daca G nu este conex atunci il putem separa in doua subgrafuri disjuncte \( G_{1} \) si \( G_{2} \), cu \( |G_{1}|+|G_{2}|=n \). Deci din pasul de inductie numarul maxim de laturi ar fi: \( |G_{1}|-1+|G_{2}|-1=n-2<n-1. \)

Mai ramane sa demonstram proprietatea daca G e conex.

Luam un varf A si vecinii acestuia \( B_{1},B_{2}\dots,B_{k} \). Fie \( S_{i},i\in\overline{1,n} \) multimile de varfuri conectate cu \( B_{i} \) printr-un drum(path) care nu trece prin A (si \( B_{i}\in S_{i}). \)

Este evident faptul ca \( S_{i} \) contin toate varfurile lui G cu exceptia lui A.

Mai mult multimile \( S_{i},i\in\overline{1,n} \) sunt disjuncte (in caz contrar ar exista un varf \( X\in S_{i}\cap S_{j} \). Cum G este conex atunci ar exista ciclul: \( AB_{i}...X...B_{j}A \), contradictie!). De aici se obtine ca: \( \sum^n_{i=1}|S_{i}|=n-1. \)

De asemenea \( S_{i} \) si \( S_{j} \) nu sunt conectate (in caz contrar exista \( X\in S_{i} \) si \( Y\in S_{j} \) conectate. Atunci ar exista ciclul: \( AB_{i}...X...Y...B_{j}A \), din nou contradictie!).

Atunci numarul maxim de muchii al lui G este:

\( k+|S_{1}|-1+|S_{2}|+\dots+|S_{k}|-1=k+n-1-k=n-1. \) (unde \( k \) reprezinta numarul muchiilor din \( A \)). Deci din inductie problema este rezolvata.