3
$\begingroup$

Let $G$ be a complete graph. Prove that there always exists a way to assign $n(n-1)/2$ directed edges in a way that the graph will be acyclic (it will contain no directed circle). In other words, prove that every complete graph can be acyclic.

To clarify what I mean: Here's an example of one valid assignment for a 4-vertices complete graph:

enter image description here

It is acyclic, it is complete.

The only observation I have made is that the in-degrees for A-B-D-C respectively are 0,1,2,3; while the out-degrees for A-B-D-C respectively are 3,2,1,0, but don't really know whether it helps me to prove this.

Any clues?

Thank you in advance and sorry if some of the terms I have used aren't accurate, I'm not taking this course in English.

$\endgroup$
5
$\begingroup$

Assign the numbers $1,\ldots,n$ to the vertices, and for $i\ne j$, let an arrow point from vertex $i$ to vertex $j$ if and only if $i<j$. That's acyclic.

$\endgroup$
1

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.