figure note that digraph may have more than one topological ordering figure two topological orderings of the same acyclic digraph proposition has topological ordering if and only if it is acyclic justificationthe necessity (the "only ifpart of the statementis easy to demonstrate suppose is topologically ordered assumefor the sake of contradictionthat has cycle consisting of edges (vi vi )(vi vi )(vik vi because of the topological orderingwe must have ik which is clearly impossible thusmust be acyclic we now argue the sufficiency of the condition (the "ifpartsuppose is acyclic we will give an algorithmic description of how to build topological ordering for since is acyclicmust have vertex with no incoming edges (that iswith in-degree let be such vertex indeedif did not existthen in tracing directed path from an arbitrary start vertex we would eventually encounter previously visited vertexthus contradicting the acyclicity of if we remove from together with its outgoing edgesthe resulting digraph is still acyclic hencethe resulting digraph also has vertex with no incoming edgesand we let be such vertex by repeating this process until the digraph becomes