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
Iets anders - donderdag 16 mei 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.
Re: De complementgraaf en de subgraaf 