Bevisa att en uppsättning bågar inte kan bilda en graf

[Ni9e]

Hej!

 

Grafen som ska bildas ska vara en oriktad, loop-fri icke-multigraf.

Det man får veta i problemet är att följande uppsättning med grad-tal på noder aldrig kan bilda en graf och det går ut på att man ska bevisa detta.

Grad-tal på noderna : {7,6,3,3,2,1,1,1}.

 

Summations principen hjälper en inte här, dvs den lag som säger att en graf måste ha ett jämnt antal noder med udda grad-tal, det har denna uppsättning bågar men det kan ändå inte bilda någon graf (prova rita så ser du själv).

 

Är det någon som kan visa hur man visar att denna uppsättning av bågar inte kan bilda en graf?

 

Tacksam för svar,

/Ni9e

 

[monstergurkan]

eftersom du har ett hörn med grad 7 så måste det hörnet ha en kant till varje annat hörn, eftersom hörnen är 8 till antalet. då har vi använt de tre hörnen med gradtal 1, använt upp en av kanterna till hörnen med grad 2, 3, 3 och 6. observera att hörnet med grad 6 bara har 5 kanter kvar att få. dock gar vi bara 3 hörn kvar, eftersom hörnen 7,1,1,1 redan är använda. och eftersom det ej kunde vara en multigraf, kan du inte ha fem kanter till tre hörn.

v.s.b