|
|
|
\require{AMSmath}
Graaf met minimumgraad d2
Beste
Ik moet het volgende bewijzen: Zij a een element van de natuurlijke getallen zonder 0, en G een graaf met minimumgraad d>2 en taille g=2a+1. Dan is |V(G)|\ge(d(d-1)^a-2)/(d-2). Mijn poging was om uit het ongerijmde te vertrekken om de ongelijkheid aan te tonen maar ik kon de contradictie niet vinden. Ik weet eigenlijk niet zo goed hoe ik de taille kan gebruiken. Kunt u me aub op de juiste weg zetten. Alvast dank ik u bij voorbaat.
Met vriendelijke groeten
Rafik
Rafik
Student universiteit België - woensdag 17 februari 2021
Antwoord
Neem een vast punt v en voor i=0,1, \dots,a laat V_i de punten zijn op afstand i van v (dus V_0=\{v\}).
De vereniging V_0\cup V_1\cup\cdots\cup V_{a-1} met alle lijnen uit de graaf ertussen is een boom, want er zit geen cykel in, en voor i=1,\dots,a-1 heeft elk punt in V_i precies één buur in V_{i-1} en ten minste d-1 buren in V_{i+1}.
Dus kun je |V_i| onderschatten:
|V_0|=1, |V_1|\ge d, |V_2|\ge d(d-1), \dots, |V_i|\ge d(d-1)^{i-1}, \dots, |V_a|\ge d(d-1)^{a-1}.
Nu optellen.
kphart
|
Vragen naar aanleiding van dit antwoord? Klik rechts..!
vrijdag 19 februari 2021
|
|
home |
vandaag |
bijzonder |
gastenboek |
statistieken |
wie is wie? |
verhalen |
colofon
©2001-2025 WisFaq - versie 3
|
