Începuturile teoriei
graficele pot fi găsite în L. Euler (1707-1783). În 1736 a fost angajat în sarcina de a traversa toate cele 7 poduri din Kaliningrad fără a trece 1 pod de două ori. Euler a transformat această sarcină în sarcina de a desena o imagine într-o singură lovitură și, cu aceasta, și-a dovedit irezolvabilitatea. În același timp, a oferit un ghid general pentru rezolvarea unei probleme de tip similar. În matematică și nu numai, întâlnim adesea obiecte care sunt într-un fel conectate de alte obiecte. De exemplu, vârfurile unui poliedru conectat prin margini, atomii elementelor conectate prin legături, nodurile de transport conectate prin drumuri sau persoanele conectate prin relații reciproce. Aceste exemple duc la
următoarele definiții: Numim grafic un set format din elemente de două feluri: primul dintre ele se numește vârfuri, care sunt legate de elemente de al doilea fel, pe care le numim margini. O margine care se ridică și intră într-un vârf se numește buclă. Dacă marginea unește vârfurile u și v, spunem că este cu acestea
vârf incident. Dacă mai multe muchii au capete comune, ele se numesc capete multiple. Graficele cu un număr finit de vârfuri și muchii se numesc finite. Acestea pot fi reprezentate într-un plan, de exemplu prin inele și linii. Această ilustrație se numește diagramă grafică. Numărul de muchii incidente cu un anumit vârf se numește gradul acelui vârf.
Vârfuri
0 grade se numesc izolate. Dacă toate vârfurile au un grad de grafic, graficul se numește grafic de gradul al n-lea. Un grafic se numește complet sau complet dacă nu conține bucle și la fiecare două vârfuri ale acelui grafic sunt conectate de exact o margine. Graficele G și G´ se numesc izomorfe dacă vârfurile lui G pot fi atribuite bijectiv vârfurilor graficului
Cercul care conține toate vârfurile grafului se numește hamiltonian. Linia care conține toate marginile grafului se numește euleriană. O împingere euleriană închisă într-un grafic G există chiar atunci când G este continuu și toate vârfurile sale sunt de grad egal. Dacă G are doar două vârfuri, acesta conține un impuls eulerian deschis. Un grafic fără cercuri înconjoară o pădure, dacă este continuă - un copac. Arborele care conține toate vârfurile graficului se numește scheletul graficului.