De digitale vraagbaak voor het wiskundeonderwijs

home |  vandaag |  gisteren |  bijzonder |  gastenboek |  wie is wie? |  verhalen |  contact

HOME

samengevat
vragen bekijken
een vraag stellen
hulpjes
zoeken
FAQ
links
twitter
boeken
help

inloggen

colofon

  \require{AMSmath} Printen

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-2024 WisFaq - versie 3