Na figura ao lado temos que os vertices $0$ e $1$ são adjacentes. A aresta que os liga, denotada por $a$ diz-se incidente de cada um desses vértices.

Os vértices ou arestas não adjacentes aos pares são chamados de independentes.

Formalmente, temos que um conjunto de vértices ou de arestas é independente se não houver dois de seus elementos adjacentes. Os conjuntos independentes de vértices também são chamados de conjuntos estáveis.

Se todos os vértices de $G$ são adjacentes aos pares, $G$ é dito completo. Esses grafos são designados por $K^{n}$ , onde $n$ é a ordem do grafo. A título de curiosidade um grafo de ordem $3 (K^{3})$ é chamado de triângulo.

Brincadeiras a parte, uma das informação mais importantes e útil sobre um grafo é o grau de um vértice. Seja $G$ um grafo , definimos o grau, degree do inglês, de um vértice $v$ de $G$ como a quantidade de arestas que incidem nele, e denotamos tal quantidade como $d(v)$.

O vertice $(1)$ presente no grafo ao lado, por exemplo, tem duas arestas incidentes, portanto seu grau é $2$. Os vértices $0$ e $2$ tem apenas uma aresta incidente cada, sendo assim, ambos são de grau $1$.

Dessa forma, o grau máximo do grafo é $2$ e o grau mínimo deste é $1$.

A ordem de um grafo $G$ é dada pela cardinalidade do conjunto de vértices $|V(G)|$, ou seja, pelo número de vértices de $G$. Além disso, o número de arestas de um grafo é dado por $|A(G)|$.

OBS: Um grafo é dito ser regular quando todos os seus vértices têm o mesmo grau.