De grens

Mocht de Erdös-Sós Conjecture waar zijn, dan is de grens 'tight'.Dit betekent dat wanneer
#E = #V(k-2)/2 er een graaf bestaat die niet iedere boom van orde k bevat. Hieronder vind je een voorbeeld dat dit bevestigt.

Voorbeeld

Zij G = (V,E) een graaf, zodanig dat #V = m(k-1), met m een natuurlijk getal en G is de disjuncte vereniging van m volledige grafen van orde k-1. Duidelijk geldt voor deze graaf dat #E = #V(k-2)/2 en G bevat geen enkele boom van orde k.

© 2014 Mark Coumans
Template design by Andreas Viklund / Best hosted at www.svenskadomaner.se