Care este suma gradelor unui graf complet cu n noduri?

Matricea de adiacenţă a unui graf neorientat G are numărul valorilor de 1 egal cu jumătate din numărul valorilor de 0. Care dintre numerele de mai jos poate fi numărul de noduri ale grafului G?

Fie un graf neorientat cu 25 noduri și 40 muchii. Precizați care este numărul maxim de noduri izolate pe care le poate avea graful.

Un graf neorientat cu n varfuri care are proprietatea ca oricare doua noduri diferite sunt adiacente se numeste graf....

Se consideră un graf neorientat cu nodurile numerotate de la 1 la 5 și muchiile [1,2],[1,5], [2,3],[2,4],[2,5],[3,4],[4,5]. Numărul lanțurilor distincte de lungime 3 de la nodul 1 la 4 este:

Se consideră un graf neorientat cu 10 vârfuri numerotate de la 1 la 10, graf cu proprietatea că există muchie între vârfurile i și j dacă și numai dacă i și j sunt numere prime între ele. Care este suma gradelor vârfurilor acestui graf?

Fie un graf neorientat cu 100 noduri. Precizați care este numărul minim de muchii necesar pentru ca graful să nu aibă noduri izolate.

Într-un graf neorientat cu 13 noduri, fiecare nod are gradul d. Valoarea lui d nu poate fi:

Un graf neorientat G cu 4 noduri, numerotate de la 1 la 4, are mulțimea muchiilor {[1,2],[2,3]}. Se construiesc toate subgrafurile distincte ale lui G având zero muchii. Două subgrafuri se consideră distincte dacă au mulțimile nodurilor diferite.

Precizați câte astfel de subgrafuri distincte ale lui G s-au construit (se numără numai subgrafurile lui G în care mulțimea muchiilor este mulțimea vidă).

Precizați câte grafuri neorientate distincte, cu nodurile etichetate de la 1 la 8, se pot construi, știind că în fiecare graf construit se respectă simultan proprietățile de mai jos:

1) Fiecare nod etichetat cu un număr prim este adiacent cu nodul 8.

2) Nu există nicio muchie [x,y] cu ambele extremități x și y numere impare.

Două grafuri neorientate se consideră distincte dacă au matricele de adiacență diferite.

Un graf neorientat are gradele vârfurilor: 2, 3, 3, 2, 4. Numărul de muchii ale grafului este:

În matricea de adiacență asociată unui graf neorientat cu n noduri, numărul de cifre de 1 aflate sub diagonala principală este egal cu n*(n-1)/2. Numărul de muchii ce trebuie adăugate la acest graf astfel încât acesta să devină complet este:

Numim graf complementar al unui graf neorientat G graful neorientat G1 cu aceeaşi mulţime a nodurilor ca şi G şi cu proprietatea că două noduri sunt adiacente în G1 dacă şi

numai dacă nu sunt adiacente în G. Dacă G are n noduri şi m muchii, câte muchii are G1?

Un graf este bipartit dacă nodurile lui pot fi împărțite în două submulțimi disjuncte, astfel încât fiecare muchie are o extremitate în prima submulțime și cealaltă în a doua

submulțime. Fie G un graf neorientat, bipartit, cu 10 noduri. Numărul maxim de muchii pe care poate să le aibă graful G este?