Solve Directed Graphs Problem 4: Construct Bipartite Graph H

[roadrunner]

Problem 4. Let k be an integer and let D be a directed graph with the property that
deg+(v) = k = deg-(v) for every v IN V (D). Prove that there exist vertex disjoint directed
cycles C1,...Ck so that SUm of V(Ci) = V (D). (HInt: construct a bipartite graph H from D
so that each vertex in D splits into two vertices in H.)

No idea how to even start...

Def: A transitive tournament is a tournament with no directed cycles. Equivalently, it is
a tournament so that the vertices can be ordered v1; v2,...vn so that (vi, vj) is an edge
whenever i < j.

Problem 6. Let T be a tournament on n vertices. Prove that T contains a subgraph which is a transitive tournament on log2n + 1 vertices.

I have no idea how to do it, i made a ton of graphs with up to 8 vertices and found subgraphs that work, but can't find any way to prove this.


So confused

 

[lippyka]

about this problem.Solution: Let T be a tournament on n vertices. We can prove that T contains a subgraph which is a transitive tournament on log2n + 1 vertices by induction on n. Base Case: When n = 1, the only possible tournament is the empty graph, which has no edges and is thus a transitive tournament on log2n + 1 = 1 vertices. Inductive Step: Assume that the statement is true for some n ≥ 1 and consider a tournament T on n+1 vertices. Since T has n+1 vertices, we can partition the vertices into two sets V1 and V2 of size n1 = ⌊(n+1)/2⌋ and n2 = ⌈(n+1)/2⌉ respectively. By the induction hypothesis, T[V1] contains a subgraph which is a transitive tournament on log2n1 + 1 vertices and T[V2] contains a subgraph which is a transitive tournament on log2n2 + 1 vertices. Now, let T' be the subgraph of T consisting of the edge (u,v) where u ∈ V1 and v ∈ V2. Note that T' has n1 + n2 − 1 = n edges, so it is a tournament on n vertices. Furthermore, any two vertices in T' can be ordered in a transitive order, since the edges in T' are all of the form (u,v) where u ∈ V1 and v ∈ V2. Thus, T' is a transitive tournament on log2n + 1 vertices. Therefore, T contains a subgraph which is a transitive tournament on log2n + 1 vertices, as desired.