graf spójny

[aGabi94]

Ile cykli ma graf spójny, w którym \(\displaystyle{ |V|=|E|}\) (gdzie \(\displaystyle{ |V|}\) -liczba wierzchołków, \(\displaystyle{ |E|}\)-liczba krawędzi)?
Czyli żeby spełniony był ten warunek możemy wziąć poszczególne cykle, np. \(\displaystyle{ C_{3}, C_{5}}\) itd., tak? Wtedy mamy 1 cykl. Jeżeli weźmiemy jakieś drzewo to możemy dorysować jeszcze jedną krawędź, żeby warunek był spełniony, dobrze myślę?Czy są jeszcze jakieś przypadki że tych cykli będzie więcej?

[mostostalek]

Zauważ, że minimalny (co do liczby krawędzi) graf spójny ma \(\displaystyle{ e=v-1}\) krawędzi gdzie \(\displaystyle{ e[/tex/ - liczba krawędzi, [tex]v}\) - liczba wierzchołków.. Taki graf nie ma żadnego cyklu.. W związku z tym odpowiedź nasuwa się sama.. Jeśli dorzucisz kolejną krawędź utworzysz dokładnie jeden cykl.