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

Re: Re: De complementgraaf en de subgraaf

 Dit is een reactie op vraag 70339 
Het moet zijn: een deelgraaf met 8 knooppunten en deze knooppunten hebben alle graad 6. Volgens mij is de oplossing: G1 heeft alle 8 punten van Gc, met graad 6. De andere twee knooppunten, van Gc, van graad vijf zitten niet meer in G1. Dit betekent dat de 10 lijnen van deze 2 punten niet meer verbonden zijn met die andere 8 punten; dus in G1 heb je 29 (lijnen van Gc)-10=19 lijnen in G1. Dit is het geval als alle 10 lijnen van deze 2 punten verbonden zijn met de resterende 8 punten. Maar het kan ook zijn dat deze twee punten met elkaar verbonden zijn (dit is 1 lijn) en de resterende 9 lijnen verbinden de 2 punten met die andere 8 punten; in dit geval heeft G1 29-9=20 lijnen.

De 2 punten van graad 5 zitten niet meer in G1. Stel dat deze 2 punten met elkaar verbonden waren in Gc, dan hadden ze ieder nog 4 lijnen over (die ooit verbonden waren met een knooppunt uit de verzameling van 8 punten). Hier wil ik bewijzen dat de deg(v) in G1 dan minstens vier is maar ik weet niet hoe ik de redenering moet afmaken.

viky
Iets anders - maandag 27 mei 2013

Antwoord

Je eerste redenering is in orde. De overige acht punten hadden in $G^c$ allemaal graad $6$. Neem zo'n punt, vanuit dat punt gaan hooguit twee lijnen naar de twee weggelaten punten, dus in $G_1$ is zijn graad ten minste $6-2=4$.

kphart
Vragen naar aanleiding van dit antwoord? Klik rechts..!
vrijdag 31 mei 2013



klein |  normaal |  groot

home |  vandaag |  bijzonder |  gastenboek |  statistieken |  wie is wie? |  verhalen |  colofon

©2001-2022 WisFaq - versie 3