Dla jakich wartości pełny graf jest podgrafem

[lola456]

1 ) Dla jakich wartości m,n (całkowite+) pełny graf dwudzielny \(\displaystyle{ K _{n,n} }\) ,n jest podgrafem grafu pełnego \(\displaystyle{ K _{n} }\)?
2 ) Dla jakich wartości n (całkowite+) cykl \(\displaystyle{ C _{n}}\) jest podgrafem pełnego grafu dwudzielnego \(\displaystyle{ K _{n,n}}\) ?

Niestety nie mam zielonego pojęcia od czego zacząć w tym zadaniu.
Zaczynam to sprawdzać dla początkowych wartości n, i w pierwszym pytaniu otrzymuję m = 2n. Czy mógłby ktoś pomóc?

[arek1357]

Coś jest nie tak, bo pełny graf dwudzielny ma cykl Hamiltona, jeżeli:

\(\displaystyle{ |V_{1}|=|V_{2}|}\)

[lola456]

Coś jest nie tak, bo pełny graf dwudzielny ma cykl Hamiltona, jeżeli:

\(\displaystyle{ |V_{1}|=|V_{2}|}\)

A jaki związek z tym zadaniem ma cykl Hamiltona? Bo nie widzę jakoś związku?

[kerajs]

1 ) Dla jakich wartości m,n (całkowite+) pełny graf dwudzielny \(\displaystyle{ K _{n,n} }\) ,n jest podgrafem grafu pełnego \(\displaystyle{ K _{n} }\)?

Dziwne jest to zadanko. Nigdzie nie występuje \(\displaystyle{ m}\) , a \(\displaystyle{ K _{n,n} }\) ma dwa razy więcej wierzchołków niż graf którego ma być podgrafem.

2 ) Dla jakich wartości n (całkowite+) cykl \(\displaystyle{ C _{n}}\) jest podgrafem pełnego grafu dwudzielnego \(\displaystyle{ K _{n,n}}\) ?

Tu wiadomo, że \(\displaystyle{ n}\) nie może być nieparzyste (gdyż pierwszy i przedostatni wierzchołek cyklu byłby w tym samym zbiorze wierzchołków między którymi nie ma krawędzi),a dla \(\displaystyle{ n=2}\) jest za mało krawędzi.
Dla każdego większego od 2 parzystego \(\displaystyle{ n}\) istnieje taki cykl (choćby taki, co wyglada jak klasyczne sznurowanie buta).

[arek1357]

Bo w zadaniu była mowa o cyklu więc zapodałem warunek na cykl Hamiltona a zresztą Kerjas ma racje bo nie bardzo wiadomo o co tu biega...
A napisałem to co można było wywnioskować...

[lola456]

1 ) Dla jakich wartości m,n (całkowite+) pełny graf dwudzielny \(\displaystyle{ K _{n,n} }\) ,n jest podgrafem grafu pełnego \(\displaystyle{ K _{n} }\)?

Dziwne jest to zadanko. Nigdzie nie występuje \(\displaystyle{ m}\) , a \(\displaystyle{ K _{n,n} }\) ma dwa razy więcej wierzchołków niż graf którego ma być podgrafem.

Tak rzeczywiście jest literówka, chodziło o graf pełny \(\displaystyle{ K _{m} }\)

Dodano po 45 sekundach:

Bo w zadaniu była mowa o cyklu więc zapodałem warunek na cykl Hamiltona a zresztą Kerjas ma racje bo nie bardzo wiadomo o co tu biega...
A napisałem to co można było wywnioskować...

Tak, ma być graf pełny \(\displaystyle{ K_{m} }\).

[kerajs]

Wobec tego odpowiedź w 1) jest trywialna: \(\displaystyle{ 2n \le m}\)

Konstrukcja grafu \(\displaystyle{ K_{n,n}}\) :
Z \(\displaystyle{ K_m}\) wybierasz \(\displaystyle{ n}\) wierzchołków i zaznaczasz je jednym kolorem (np: na niebiesko), z pozostałych wierzchołków wybierasz kolejne \(\displaystyle{ n}\) wierzchołków i zaznaczasz je innym kolorem (np: na czerwono). Jeszcze innym kolorem (np: zielonym) poprawiasz wszystkie krawędzie łączące wierzchołki o różnych kolorach. Uzyskany, kolorowy graf jest pełnym grafem dwudzielnym \(\displaystyle{ K_{n,n}}\) .

[lola456]

Nie pomyślałam, żeby pokolorować wierzchołki, tylko się męczyłam "na około".
Czasem najprostsze rozwiązania są najtrudniejsze.
Dziękuję bardzo za pomoc.