WisFaq!

De complementgraaf en de subgraaf

Beste wisfaq,

Ik heb een graag met 10 knooppunten en 10 lijnen. Stel dat deze graaf 8 knooppunten heeft van graad 3 en 2 knooppunten van graad 4.

Dan heeft de complementgraaf 8 knooppunten van graad 6 en twee knoopunten van graad 5. Hier gebruik ik dat de graad van een knooppunt v in een complementgraaf, Gc, wordt gegeven door n-k-1, met n het aantal knooppunten, en k de graad van een knooppunt v in de oorspronkelijke graaf G.
Subgraaf
Stel nu dat G1 een subgraaf is van Gc die bestaat uit 6 knooppunten van graad 8. Dan heeft G1

(1) 19 of 20 lijnen en
(2) de graad van ieder knooppunt is minstens 4.

Dit begrijp ik niet. Er geldt dat 2*E=SOM(deg(v)), v een knooppunt in de knooppuntenverzameling V van graaf G, E is het aantal lijnen in G.
Dus voor G1: 2E=6*8, dus er zijn 24 lijnen.
En waarom moet de graad van iedere v in G1 minstens 4 zijn ?

Complementgraaf, G1c, van de subgraaf G1
Voor G1C geldt:
(3) deg(v in G1c) is hoogstens 3 (voor elke v in G1c)
Dit begrijp ik niet want G1c heeft 6 knooppunten en k=deg(v in G1)>=4, dus deg(v in G1c)=n-k-1=6-4-1=1.

Ik begrijp niet waar ik de fouten maak.

Vriendelijke groeten,dank,

Viky

Viky
16-5-2013

Antwoord

Het enige dat ik kan bedenken is dat de grafen boven en onder het woord `Subgraaf' niets met elkaar te maken hebben.
De graaf aan het begin is een onmogelijke: uit de aannamen over de graden volgt dat de graaf $16$ lijnen heeft, maar het gegeven is dat er $10$ zijn.
De tweede graaf, na `Subgraaf', moet een totaal andere zijn.
Bekijk je gegevens nog eens goed.

kphart
19-5-2013