1. LEMA ("Lema do vértice de grau de entrada zero"): se G=(V,E) é um grafo direcionado sem circuitos e com pelo menos um vértice, então G possui pelo menos um vértice de grau de entrada igual a zero.

========================================================
--------------------- PROVA LEMA 1 ---------------------
Suponha, por absurdo, que o enunciado é falso para um certo grafo G.
Nós mostraremos então o seguinte resultado, por indução em "k":

* Afirmação: para todo natural positivo "k", existe uma sequência <v_1, v_2, ..., v_k> de vértices DISTINTOS de G tal que, para todo natural positivo i<k, (v_{i+1},v_i) \in E.

================================
------ PROVA DA AFIRMAÇÃO ------
* Base (k=1): o resultado é trivial, pois, sendo "v" um vértice qualquer de G (observe que, pelo enunciado, |V| >= 1), a sequência <v> satisfaz a propriedade desejada (por vacuidade), CQD.
* Passo (k=j+1, j>=1): pela hipótese de indução, existe uma sequência <v_1, v_2, ..., v_j> de vértices distintos de G tal que, para todo natural positivo i<j, (v_{i+1},v_i) \in E. Agora, pela hipótese inicial, v_j não possui grau de entrada igual a zero, isto é, existe um par (x,v_j) em "E". Dado um tal "x", observe que "x" não pode estar na sequência <v_1, v_2, ..., v_j>, pois, se estivesse, então a sequência <x,v_j,v_{j-1},...,v_{i+1},v_i>, com x = v_i, seria um circuito em G, um absurdo, já que G não possui circuitos. Logo, a sequência <v_1, v_2, ..., v_j,x> satisfaz a propriedade desejada, CQD.
------ PROVA DA AFIRMAÇÃO ------
================================

Logo, pela afirmação acima, sendo n = |V|, há uma sequência <v_1,v_2,...,v_{n+1}> de vértices distintos de G, um absurdo, pois G possui apenas "n" vértices.
Logo, a suposição inicial de que o enunciado é falso é falsa, CQD.
--------------------- PROVA LEMA 1 ---------------------
========================================================


2. LEMA: se G=(V,E) é um grafo direcionado sem circuitos de n >= 1 vértices, então G possui uma ordenação topológica.

========================================================
--------------------- PROVA LEMA 2 ---------------------
Por indução em "n".
* Base (n=1): se V={v}, então <v> é uma ordenação topológica de G, CQD.
* Passo (n=n'+1, n'>=1): como G não possui circuitos, então, pelo lema 1 acima, existe pelo menos um vértice "v" de G cujo grau de entrada é zero. Seja então "v" um tal vértice, e seja G' o grafo que se obtém removendo-se "v" de "G". Logo, G' tem n' vértices, e, pela hipótese de indução, G' possui uma ordenação topológica. Seja então <v_1,v_2,...,v_{n'}> uma ordenação topológica de G'; nós argumentamos que <v,v_1,v_2,...,v_{n'}> é uma ordenação topológica de G. De fato, dada uma aresta (x,y) de G, temos que y != v, pois "v" possui grau de entrada igual a zero. Logo, ou (x,y) é aresta de G' ou x=v. Se x=v, então y certamente está depois de x na ordem em questão, pois v é o primeiro vértice da ordem, cqd. Em caso contrário (x != v), então (x,y) é aresta de G', e, nesse caso, como <v_1,v_2,...,v_{n'}> é ordenação topológica de G', então y ocorre depois de x em <v_1,v_2,...,v_{n'}>, e portanto também em <v,v_1,v_2,...,v_{n'}>, CQD.
--------------------- PROVA LEMA 2 ---------------------
========================================================


3. LEMA: um grafo direcionado G = (V,E) tal que |V| >= 1 tem pelo menos um circuito sse G não possui ordenação topológica.

========================================================
--------------------- PROVA LEMA 3 ---------------------
IDA: temos que mostrar que, se há circuito, então não há ordenação topológica.
Seja então um circuito C de G.
Seja também v_1, ..., v_n uma ordenação qualquer de "V"; nós mostraremos que ela não é topológica.
De fato, seja "i" o maior natural "i" tal que v_i está em C.
Além disso, seja "v_j" o sucessor de v_i em C.
Logo, (v_i,v_j) \in E. Além disso, pela escolha de "i", j < i.
Logo, a ordenação em questão não é topológica, CQD.

VOLTA: temos que mostrar que, se não há ordenação topológica, então há circuito.
De fato, suponha que não há ordenação topológica; nós mostraremos que há circuito.
Suponha, por absurdo, que não há circuito.
Logo, pelo lema 2 acima, como |V| >= 1, então G possui uma ordenação topológica, uma contradição com a suposição inicial.
Logo, G tem que possuir circuitos, CQD.
--------------------- PROVA LEMA 3 ---------------------
========================================================