Fluxo máximo = 28. Um corte com esta capacidade pode ser todas as arestas que saem de s, ou todas que chegam em t. A figura a seguir mostra um fluxo máximo. Em cada aresta, temos o fluxo entre parênteses.
A figura a seguir mostra uma árvore de caminhos mínimos a partir de s (arestas mais grossas). Dentro de cada vértice, temos o valor de um caminho mínimo a partir de s.
A figura a seguir mostra uma árvore geradora mínima (arestas mais grossas). Até onde pude perceber, é única neste grafo ponderado. O peso total da árvore é 28.
A figura a seguir mostra uma coloração ótima para o grafo dado. Pensei em dois possíveis argumentos: (1) retirando o vértice 3, temos um ciclo ímpar, que requer 3 cores. Como o vértice 3 é adjacente a todos os outros, uma nova cor será necessária para ele, totalizando 4 cores; (2) suponha que três cores sejam suficientes. Comece pintando a clique {1, 2, 3} com as três cores escolhidas. A partir daí, é forçada a cor de 7, 6, 4, 5, nesta ordem. Daí chegamos ao vértice 8, que é adjacente a três vértices de cores distintas. Portanto, 3 cores não são suficientes.
