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
27-5-2013
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
31-5-2013
#70373 - Grafen - Iets anders