Dwa trójkąty
-
mol_ksiazkowy
- Użytkownik
- Posty: 13376
- Rejestracja: 9 maja 2006, o 12:35
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Podziękował: 3425 razy
- Pomógł: 809 razy
Dwa trójkąty
Udowodnić, że jeśli graf prosty ma \(\displaystyle{ 2n}\) wierzchołków i \(\displaystyle{ n^2+1}\) krawędzi, to ma on wtedy trójkąty o wspólnym boku.
-
Blazo2000
- Użytkownik
- Posty: 50
- Rejestracja: 31 gru 2017, o 11:32
- Płeć: Mężczyzna
- Lokalizacja: Bochnia
- Podziękował: 5 razy
- Pomógł: 15 razy
Re: Dwa trójkąty
Dla \(\displaystyle{ n=2}\) mamy \(\displaystyle{ 4}\) wierzchołki i \(\displaystyle{ 5}\) krawędzi więc teza jest oczywista. Weźmy \(\displaystyle{ n>2}\) oraz o dowolnych dwóch wierzchołkach połączonych krawędzią powiemy, że są znajomymi. Mamy dwie możliwości albo istnieje para znajomych, którzy nie mają wspólnego znajomego albo nie.
1. W pierwszym przypadku oznaczmy wierzchołki takiej pary jako \(\displaystyle{ a}\) i \(\displaystyle{ b}\). Skoro nie mają wspólnego znajomego to każda z pozostałych \(\displaystyle{ 2n-2}\) osób zna maksymalnie jedną osobę z pary \(\displaystyle{ a}\) i \(\displaystyle{ b}\), stąd liczba krawędzi wychodzących z \(\displaystyle{ a}\) i \(\displaystyle{ b}\) do pozostałych wierzchołków nie przekracza \(\displaystyle{ 2n-2}\). Dodając do tego krawędź między nimi stwierdzamy, że usuwając z grafu te dwa wierzchołki i wszystkie krawędzie z nimi związane usuniemy maksymalnie \(\displaystyle{ 2n-1}\) krawędzi. Dostaniemy zatem graf o \(\displaystyle{ 2(n-1)}\) wierzchołkach oraz przynajmniej \(\displaystyle{ n^2+1-(2n-1)=n^2-2n+1+1=(n-1)^2+1}\) krawędziach, następnie w miarę potrzeby możemy usunąć jeszcze krawędzie aż będzie ich dokładnie \(\displaystyle{ (n-1)^2+1}\). Na mocy założenia indukcyjnego w otrzymanym grafie są takie dwa trójkąty, a skoro jest on podgrafem wyjściowego grafu to w nim również były.
2. W drugim przypadku jeśli taka para znajomych nie istnieje to znaczy, że każda para znajomych ma wspólnego znajomego, innymi słowy każda krawędź grafu należy do jakiegoś trójkąta. Niech \(\displaystyle{ X}\) oznacza ilość wszystkich trójkątów w naszym grafie, przypuśćmy że wypisujemy dla wszystkich trójkątów po kolei wszystkie ich trzy krawędzie w jednym ciągu. W ten sposób wypiszemy \(\displaystyle{ 3X}\) krawędzi, skoro każda krawędź należała do jakiegoś trójkąta to każda została wypisana co najmniej raz, z drugiej strony gdyby wszystkie zostały wypisane dokładnie raz to ich ilość, czyli \(\displaystyle{ n^2+1}\) dzieliłaby się na \(\displaystyle{ 3}\), co jest niemożliwe, zatem co najmniej jedna krawędź została wypisana przynajmniej dwukrotnie, czyli należy do co najmniej dwóch różnych trójkątów, co kończy dowód także w tym przypadku.
1. W pierwszym przypadku oznaczmy wierzchołki takiej pary jako \(\displaystyle{ a}\) i \(\displaystyle{ b}\). Skoro nie mają wspólnego znajomego to każda z pozostałych \(\displaystyle{ 2n-2}\) osób zna maksymalnie jedną osobę z pary \(\displaystyle{ a}\) i \(\displaystyle{ b}\), stąd liczba krawędzi wychodzących z \(\displaystyle{ a}\) i \(\displaystyle{ b}\) do pozostałych wierzchołków nie przekracza \(\displaystyle{ 2n-2}\). Dodając do tego krawędź między nimi stwierdzamy, że usuwając z grafu te dwa wierzchołki i wszystkie krawędzie z nimi związane usuniemy maksymalnie \(\displaystyle{ 2n-1}\) krawędzi. Dostaniemy zatem graf o \(\displaystyle{ 2(n-1)}\) wierzchołkach oraz przynajmniej \(\displaystyle{ n^2+1-(2n-1)=n^2-2n+1+1=(n-1)^2+1}\) krawędziach, następnie w miarę potrzeby możemy usunąć jeszcze krawędzie aż będzie ich dokładnie \(\displaystyle{ (n-1)^2+1}\). Na mocy założenia indukcyjnego w otrzymanym grafie są takie dwa trójkąty, a skoro jest on podgrafem wyjściowego grafu to w nim również były.
2. W drugim przypadku jeśli taka para znajomych nie istnieje to znaczy, że każda para znajomych ma wspólnego znajomego, innymi słowy każda krawędź grafu należy do jakiegoś trójkąta. Niech \(\displaystyle{ X}\) oznacza ilość wszystkich trójkątów w naszym grafie, przypuśćmy że wypisujemy dla wszystkich trójkątów po kolei wszystkie ich trzy krawędzie w jednym ciągu. W ten sposób wypiszemy \(\displaystyle{ 3X}\) krawędzi, skoro każda krawędź należała do jakiegoś trójkąta to każda została wypisana co najmniej raz, z drugiej strony gdyby wszystkie zostały wypisane dokładnie raz to ich ilość, czyli \(\displaystyle{ n^2+1}\) dzieliłaby się na \(\displaystyle{ 3}\), co jest niemożliwe, zatem co najmniej jedna krawędź została wypisana przynajmniej dwukrotnie, czyli należy do co najmniej dwóch różnych trójkątów, co kończy dowód także w tym przypadku.