Um grafo (simples) $G$ consiste em um conjunto finito e não vazio $V(G)$ de objetos chamados vértices, juntamente com um conjunto $A(G) ($ou, equivalentemente, $E(G))$ de pares não ordenados de vértices; os elementos de $A(G)$ são chamados de arestas. Podemos representá-lo por $G = (V ; A) (G=(V,E))$, onde $V = V (G)$ e $A = A(G) ($ou, equivalentemente, $E=E(G))$.