Prove that every acyclic graph has at least one source vertex and at least one termination vertex

Question

How can i prove that every acyclic graph has at least one source vertex and one(at least) termination vertex?

Answer 1

My suggestion is: that P=(u,…v) is the maximum path of the graph D.If a vertex u is adjacent to one vertex of P, then i have a cyrcle. So its wrong. If vertex u is adjacent to one vertex which dont belong to P, then i have a new bigger path. So the vertex is not neighboring an other vertex and d(u) = 0

Answer 2

Suppose not. Then either, your graph has no sources or your graph has no sinks. Let's assume for a minute that it has no sinks. Pick a random vertex as a starting point. Walk around your graph following directed edges. There are no sinks, so you can always continue walking. But you are in a finite graph, so the pigeonhole principle says you will eventually hit the same vertex twice. That means you walked in a cycle, which is a contradiction.

If there are no sources, then replace your graph with a new one where you give every edge the opposite orientation. Now you have a graph with no sinks. The above argument gives a cycle in that graph. If you turn all the edges back around, you still have a cycle.