graf hamiltonowski z liczba krawedzi

[kamil.jack]

Niech G=(V,E) bedziue grafem gdzie |V|=n i \(\displaystyle{ |E|> \frac{n^2-3n+4}{2}}\). Pokazac ze G jest hamiltonowski
b) podac przyklad grafu \(\displaystyle{ |E|= \frac{n^2-3n+4}{2}}\), ktory nei jest hamiltonowski

[Qń]

Dowód do a) masz tutaj:


Kontrprzykładu do b) na razie nie umiem znaleźć - by to zrobić należy dla jakiegoś \(\displaystyle{ n}\) z grafu pełnego \(\displaystyle{ K_n}\) usunąć \(\displaystyle{ n-2}\) krawędzi tak, żeby w nowopowstałym grafie nie istniała droga Hamiltona. Ale cholera wie jak to zrobić i dla jakiego \(\displaystyle{ n}\) .

Q.