De Erdös-Sós Conjecture
Zij G = (V,E) een graaf. Als #E > (k-2)#V/2 dan geldt dat G iedere boom van orde k bevat.
Dit probleem kan vanuit twee kanten bekeken worden. In het begin is het namelijk handig om naar speciale gevallen te kijken. Er kan gekeken worden naar situaties waar beperkingen gelden voor de graaf G of gevallen waar beperkingen gelden voor de boom. Een vergelijkbaar probleem is de Sumner's Universal Tournament Conjecture. Dit probleem gaat over volledige grafen waarin iedere kant een richting heeft meegekregen. De conjecture zegt het volgende:
Om de artikelen over dit probleem beter te begrijpen is het aan te raden om eerst de definities te bekijken.
Dit probleem, de Erdös-Sós Conjecture, is gevonden op: AllTreesSubgraphs .
© 2014 Mark Coumans
Template design by Andreas Viklund / Best hosted at www.svenskadomaner.se