Há vários tipos de grafos, vamos enumerar alguns deles e apresentar algumas propriedades. Alguns, inclusive, já tiveram, ou terão sua própria documentação com uma descrição mais abrangente. Vamos começar pelos Grafos Triviais.

Assim sendo, um grafo de ordem $0$ ou $1$ é chamado grafo trivial. Geralmente, por definição, tratamos os grafos triviais de forma despreziva, pois formam contra-exemplos bobos e se tornam um incomômdo, mas não se engane, em algumas situações, para iniciar uma indução,por exemplo, grafos triviais podem ser muito úteis. O grafo $G$ vazio pode ser representado somente por $G = \emptyset$.

Já falamos deste tipo de grafo e o usamos para apresentar uma definição em Definições de grafos. Relembremos:

Assim sendo, um grafo simples é um grafo não direcionado, não ponderado, que não possuem laços nem mais de uma aresta ligando dois vértices,isto é, sem arestas “paralelas”. Assim, um grafo simples é um grafo que não possui arestas múltiplas. Como ,por exemplo, o grafo abaixo:

Um grafo orientado, ou digrafo, são grafos com uma diferença fundamental em relação aos grafos simples: as arestas possuem uma direção. Isso muda muito a situação e o significado do grafo estudado. Além disso, há a possibilidade da existência de arestas paralelas, ou seja, as arestas incidem nos mesmos vértices e possuem a mesma orientação. Para tanto, podemos usar a seguinte definição:

O grafo abaixo é um exemplo de um digrafo. Repare que há arestas paralelas representadas por uma seta dupla, como por exemplo,$\{5, 3\}, \{3, 5\}$.

Além da orientação, é possível atribuir custo para o vértice, para a aresta ou para ambos. O grafo que recebe esses valores são chamados grafos ponderados. Um grafo valorado $G(V,A)$ consiste de um conjunto finito não vazio de vértices $V$, ligados por um conjunto $A$ de arestas com pesos.

O conjunto $A$ consiste de triplas distintas da forma $(v,w, valor)$, em que $v$ e $w$ são vértices pertencentes a $V$ e $valor$ é um número real$(ℝ)$.

O grafo acima é um exemplo de grafo ponderado, com vértices $x, y,w ∈ V$, com as arestas $xy$, $xw$ e $yw$, recebendo os valores 5,9 e 4, respectivamente. Podemos também colocar valores para os vértices caso deja do nosso interesse, logo os valores de $x,y$ e $w$ são mutáveis.

Um grafo completo é aquele em que todos os seus vértices são adjacentes aos pares, ou seja, existem arestas presentes entre todos os pares de vértices. Um grafo completo $K_n$ possui $$\frac{n(n-1)}{2}$$ arestas, como veremos mais a frente como um resultado do corolário do Lema do Aperto de Mão.

Abaixo um exemplo de grafo completo:

O grafo abaixo por exemplo é um grafo conexo:

E o pŕoximo, é um exemplo de grafo desconexo: