Combinatorics/graph theory: Digraphs and cycles


by KroneckerDelta
Tags: cycles, digraphs, theory
KroneckerDelta
KroneckerDelta is offline
#1
Jan9-13, 12:38 PM
P: 1
Hi,

How would you go about proving the following statement?

Let k:= ∂+(D) with k≥ 1. Then D contains a cycle of length at least k+1.

∂+(D) is the minimum out degree of any vertex in digraph D.

Thanks a lot, Will
Phys.Org News Partner Science news on Phys.org
Lemurs match scent of a friend to sound of her voice
Repeated self-healing now possible in composite materials
'Heartbleed' fix may slow Web performance

Register to reply

Related Discussions
Graph theory: Existence of cycles Calculus & Beyond Homework 0
Combinatorics(Graph Theory) Calculus & Beyond Homework 0
General Help for Combinatorics and Graph Theory General Math 5
Cycles in a number-theoretic graph... Brain Teasers 1
number of cycles in a graph ??? Programming & Computer Science 0