Seja $G$ um grafo simples, dois vértices $x$ e $y$ são adjacentes, ou vizinhos, se $\{ x,y \}$ é uma aresta de $G$. Tal aresta é dita incidente a ambos, $x$ e $y$. Além, duas arestas $e ≠ f$ são adjacentes se possuem um extremos em comum.

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.

Ver também: Grau médio de um grafo.