É uma árvore enraizada ordenada em que cada vértice não folha possui exatamente m filhos, m>=1.
Quando m=2, a árvore é estritamente binária.

Subárvore Parcial
Seja Tv uma subárvore enraizada de raiz v. Seja S um subconjunto de vértices de Tv tal que Tv-S seja conexo e V não pertence S. O grafo Tv-S é denominado subárvore parcial de raiz v.

Árvore m-ária
Se T uma árvore enraizada estritamente m-ária. A cada filho w de todo vértice não folha v, atribua um rótulo inteiro positivo, r(w).
1<=r(w)<=m é a posição que w ocupa na ordenação dos filhos de v.

Uma subárvore parcial de uma árvore estritamente m-ária que possui rotulação é chamado árvore m-ária.
Por exemplo, numa árvore binária, cada filho w de v pode ser identificado como seu filho esquerdo ou direito. Naturalmente, o filho esquerdo pode existir sem o direito e vice-versa.

Planaridade
Seja G um grafo e R uma representação geométrica de G em um plano. A representação R é chamada plana quando não houver cruzamento de linhas em R-a não ser nos vértices.

Um grafo é dito planar quando admitir alguma representação plana.

As linhas de representação R dividem o plano em regiões, denominadas faces de R. Existe exatamente uma região não limitada, chamada face externa. Duas representações planas de um mesmo grafo possuem sempre o mesmo número de faces.

Teorema:
Seja G um grafo planar
Então:

n+f = m+2 ,n - vértices, f - faces, m - arestas

Lema:
Seja G um grafo planar
Então:

m <= 3n-6 

Quanto maior o número de arestas em relação ao número de vértices, mais díficil obter representações geométricas planas.

Fato:
Todo grafo planar admite uma representação plana em que todas as linhas são retas.

Lema:
Os grafos K5 e K3,3 são não planares

Subdivisão de uma aresta
Operação que transforma a aresta (v,w) num caminho v,z1,z2,...,zk,w, sendo k>=0, onde os zi são vértices de grau 2 adicionados ao grafo.

Teorema:
Um grafo é planar se e somente se não contém como subgrafo uma subdivisão de K5 ou K3,3.

Ciclo Hamiltoniano
Ciclo hamiltoniano contém cada vértice do grafo exatamente uma vez. Um grafo hamiltoniano é aquele que contém um ciclo hamiltoniano.

Coloração:
Seja G(V,E) um grafo e C={cj} um conjunto de cores. Uma coloração de G é uma atribuição de alguma cor para cada vértice de V, de modo que a dois vértices adjacentes sejam atribuidas cores diferentes.

Uma k-coloração é uma coloração que utiliza um total de k cores.

Número cromático: X(G) de um grafo G, é o menor número de cores k para o qual existe uma k coloração de G.
Coloração mímima: utiliza o número mínimo de cores.

Colorir é fácil, difícil é o problema de encontrar um processo eficiente para obtenção da coloração mínima.
Não é conhecido algoritmo eficiente para determinar o número cromático de um grafo.

Relações entre conceitos
São necessárias p cores para colorir os diferentes vértices de uma clique de tamanho k. O número cromático de um grafo G é maior ou igual que o tamanho do maior clique de G.

Considere uma k-coloração de G(V,E). Sejam v1,...,vk os subconjuntos disjuntos de V, induzidos pela k-coloração.
Então a união dos vi será V e cada vi é um conjunto independente de vértices.

Um grafo é denominado k crítico quando X(G)=k e para todo subgrafo próprio H de G, X(H)>k .

Teorema:
Se G(V,E) é k-crítico, então grau(v)>=k-1, para todo v pertencente a V.

O problema das 4 cores
O problema das 4 cores consiste em colorir os países de um mapa arbitrário plano, cada país com uma cor, de tal forma que países fronteiriços possuam cores diferentes.

O problema consiste em obter tal coloração usando não mais que 4 cores - fato provado em 1977. Seja M uma região do plano, um mapa é um particionamento de M em um número finito de sub-regiões, os quais são delimitados por linhas.

Duas regiões são adjacentes quando possuírem uma linha em comum. Uma coloração é uma atribuição de uma cor a cada região de M, de modo que regiões adjacentes possuam cores diferentes. Um mapa M é k-colorível quando existir uma coloração de M que utiliza k cores.

Excentricidade de um Grafo e Árvores

Dígrafos