Question

Sa se demonstreze ca pentru orice arbore T, ck(T) = T .

Pentru orice graf simplu conex G=(V,E), notam cu ck(G) graful simplu obtinut astfel:ck(G) = (V,E∪{xy|x,y∈centr(G),x!=y}).

Answer 1

Demonstrarea se poate face prin tehnica reducerii la absurd.

Presupunem ca exista un arbore T care sa aiba proprietatea ck(T) ≠ T.

In acest caz, graful ck(T) are cel putin doua muchii E' care nu apartin lui T.

Deci, daca luam un varf v in E', trebuie sa existe cel putin doua muchii incidente lui v care sa nu apartina lui T.

Deci exista cel putin doua varfuri care aduc cicluri in T, ceea ce contrazice definitia unui arbore.

Prin urmare, pentru orice arbore T, ck(T) = T.     1:01 PM