Rozważ 9-wierzchołkowy, prosty i spójny graf, który ma dokładnie 12 krawędzi Ania: 7. (a) Rozważ 9−wierzchołkowy, prosty i spójny graf, który ma dokładnie 12 krawędzi i 3 cykle. Narysuj ten graf lub wyjaśnij dlaczego taki graf nie istnieje. (b) Ukorzenione drzewo jest to drzewo z wyróżnionym wierzchołkiem zwanym korzeniem. Narysuj wszystkie ukorzenione drzewa, które mają 5 wierzchołków. Wskaż, które z nich są izomorficzne?

Bleee: I problem polega na

Ania: Zawsze mi wychodzi 11 krawedzi

Ania: ma ktoś pomysł ? Wychodzi mi ze w a) taki graf nie istnieje, ale nie wiem jak to udowodnic

Bleee: A możesz narysować ten graf o 11 wierzchołkach i zaznaczyć te 3 cykle?

Ania:

Bleee: Co prawda robię to w głowie, ale mi się wydaje że z 11 wierzchołkami masz 2 cykle, a z 12 będą właśnie 3 cykle

Ania: ma byc 9 wierzchołków a 12 krawedzi

Ania: ktoś coś ?

Bleee: Okey... Ja myślałem tylko o pełnych cyklach i tylko je rozpatrywanem jako cykle.

Bleee: To teraz trzeba to udowodnić. Zauważ że spójny, prosty graf nie posiadający żadnych cykli ma n−1 krawędzi. Każda następna krawędź będzie tworzyć przynajmniej jeden cykl. Tak więc, przy n+3 krawędziach będziemy mieli conajmniej 4 cykle.

Ania: oki dzieki za pomoc a pkt b) ? Ogolnie narysowalam 5 drzew ale nie wiem które są izomorficzne, wie ktoś jak to zrobic ?

Ania:

wredulus_pospolitus: i to nie są wszystkie

wredulus_pospolitus: Jeszcze masz ten ale jeden z tamtych wypada (nr 8 bo to nic innego jak nr 3)