Matematické Fórum

Na 4 vrcholech není problém takový graf najít. Jak tento příklad zobecnit? Doporučuji se na problém podívat jako na hranový rozklad grafu na dva isomorfní faktory.
Dá se ukázat, že graf (i doplněk) musí být diametru 3. To pomůže při hledání "větších" grafů.
Mimochodem: odkud je tato úloha?

↑ SweetNelli:Moje zvědavost mi nedá a ptám se znovu. Odkud je tato úloha? Stejné zadání jsem loni zařadil do textu (skript), které připravuji.

↑ SweetNelli:Navážu na svůj předchozí příspěvek. Kompozice grafu je popsána např. na http://mathworld.wolfram.com/GraphComposition.html No a když se začne zmíněným nejmenším grafem K_4 rozloženým na dvě cesty P_4 (na 4 vrcholech), tak pro každou cestu uděláme kompozici P_4[K_t] a dostaneme rozklad K_4[K_t] na dva grafy P_4[K_t] (každý z "nafouknutých" grafů je nějakým 4-partitním grafem). Teď zbývá vhodně přidat hrany dvou kompletních grafů K_t do vhodných dvou "partit" grafu P_4[K_t]. Máme dvě možnosti.
Neříkám, že to je jediné řešení, ale funguje to pro každé t. Naproti tomu určitě neexituje takový rozklad K_n pro každé n, triviálně ne když K_n má lichý počet vrcholů.

↑ Kondr:No jasně! Co jsem to napsal?!? Chtěl jsem napsat lichý počet hran, ne vrcholů!
A kompletní graf má lichý počet hran, když n(n-1)/2 je liché číslo, tedy pro n=4k+2 nebo n=4k+3.