1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
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

Can you help with the solution or looking for help too?

Similar Discussions: Directed graphs
  1. Graph Theory (Replies: 0)

  2. Graph theory (Replies: 0)

  3. Graph Theory (Replies: 0)