Register to reply 
Directed graphs 
Share this thread: 
#1
Nov3010, 08:21 PM

P: 103

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 


Register to reply 
Related Discussions  
Converting VelocityTime Graphs Into Acceleration Graphs  Introductory Physics Homework  5  
Good software for making directed graphs?  Academic Guidance  3  
Very simple calculus problem...graphs and velocity/time graphs to acceleration.  Calculus & Beyond Homework  1  
Directed sets  Calculus & Beyond Homework  3  
Equilibrium Points of Directed Graphs  General Math  4 