Grau (teoria dos grafos)
Na teoria dos grafos, o grau (ou valência) de um vértice de um grafo é o número de arestas incidentes para com o vértice, com os laços contados duas vezes. Ou de forma análoga, o número de vértices adjacentes a ele. O grau de um vértice é denotado O grau máximo de um grafo G, denotado por Δ(G), e o grau mínimo de um grafo, denotado por δ(G), são os graus máximos e mínimos de seus vértices. No grafo à direita, o grau máximo é 3 e o mínimo é 0. Em um grafo regular, todos os graus são os mesmos, e assim podemos falar de o grau do grafo [sic?].
A fórmula da soma dos graus afirma que, dado um grafo G = ( V , E ) , {\displaystyle G=(V,E),} ∑ v ∈ V deg ( v ) = 2 | E | . {\displaystyle \sum _{v\in V}\deg(v)=2|E|\,.} A fórmula implica que em qualquer grafo, o número de vértices de grau ímpar é par. Esta afirmação (bem como a fórmula de soma grau) é conhecida como o Lema do aperto de mãos (em inglês, handshaking lemma). O último nome vem de um problema matemático popular, para provar que, em qualquer grupo de pessoas o número de pessoas que apertam as mãos com um número ímpar de outras pessoas do grupo é par.
A sequência de grau de um grafo não direcionado é a sequência não crescente dos seus graus de vértices; para o grafo acima, é (3, 3, 3, 2, 2, 1, 0). A seqüência de grau é uma invariante do grafo, logo grafos isomorfos têm a mesma sequência. No entanto, a sequência de grau, em geral, não identifica unicamente um grafo; em alguns casos, os grafos não isomorfos têm o mesmo grau de sequência. O problema da sequência de graus, é o problema de encontrar alguns ou todos os grafos com a seqüência de grau sendo uma dada sequência não crescente de números inteiros positivos. Zeros finais podem ser ignorados, uma vez que são trivialmente efetuados pela adição de um número adequado de vértices isolados do grafo. O problema de encontrar ou estimar o número de grafos com uma seqüência de determinado grau é um problema do campo da enumeração de grafos. Como consequência da fórmula da soma de graus, toda a sequência com uma soma ímpar, como (3, 3, 1), não pode ser entendida como a sequência de grau de um grafo. O inverso também é verdadeiro: se uma seqüência tem uma soma par, é a seqüência de grau de um grafo. A construção de um grafo como este é simples: conecte vértices ímpares em pares, e preencha com laços (auto-loops).
