Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Directed graphs

  1. Nov 30, 2010 #1
    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
  2. jcsd
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted