Grafo regular

Em Teoria dos grafos, um grafo regular é um grafo onde cada vértice tem o mesmo número de adjacências, i.e. cada vértice tem o mesmo grau ou valência. Um grafo direcionado regular também deve satisfazer a condição mais forte de que o grau de entrada e o grau de saída de cada vértice sejam iguais uns aos outros. Um grafo regular com vértices de grau k é chamado um grafo k‑regular ou grafo regular de grau k. Grafos regulares de grau no máximo 2 são fáceis de classificar: Um grafo 0-regular é composto por vértices desconectados, um grafo 1-regular consiste de arestas desconectadas, e um grafo 2-regular consiste de ciclos desconectados. Um grafo 3-regular é conhecido como um grafo cúbico. Um grafo fortemente regular é um grafo regular, onde cada par de vértices adjacentes tem o mesmo número l de vizinhos em comum, e cada par de vértices não-adjacentes tem o mesmo número n de vizinhos em comum. Os menores grafos que são regulares, mas não fortemente regulares são os grafos ciclos e os grafos circulantes em 6 vértices. O grafo completo K m {\displaystyle K_{m}} é fortemente regular para qualquer m {\displaystyle m} . Um teorema de Nash-Williams diz que cada k‑grafo regular em 2k + 1 vértices tem um ciclo hamiltoniano.