G is a simple directed graph on n vertices and each verticle is the head of at least n/2 arcs and each vertice is the tail of at least n/2 arcs. Prove that G contains a directed Hamiltonian cycle.
I would be grateful, if you could help me!
G is a simple directed graph on n vertices and each verticle is the head of at least n/2 arcs and each vertice is the tail of at least n/2 arcs. Prove that G contains a directed Hamiltonian cycle.
I would be grateful, if you could help me!
I don't know how to prove this, but this looks similar to the Ghouila-Houiri theorem.
Consider the largest directed cycle C possible in G. If It is not Hamiltonian, then consider a vertex v not in C. Since both the in-degree and out-degree of v is more than half the size of C, there will be v' and v" in C such that the edge (v',v") is in C, and the edges (v',v) and (v,v") are in G. Can you fill in the details ?