Out-degree three and two disjoint directed cycles: where is the second cycle?
poyo_panic·
Following outgoing edges finds one cycle. Deleting its vertices can destroy the out-degree condition, so that doesn't find a disjoint second one. I'm looking for an extremal choice of the first cycle that controls the edges leaving it. Loops and two-cycles also need to be included.
Problem:
In a directed graph outgoing degree of each vertex equals (loops and bidirectional edges are allowed and considered as cycles). Prove that the graph contains non-intersecting directed cycles.
Source: Baltic Way 2019 · MNET-01FM
Open MNET-01FM in the question bank →