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
Cougars' diverse diet helped them survive the Pleistocene mass extinction
Cyber risks can cause disruption on scale of 2008 crisis, study says
Mantis shrimp stronger than airplanes

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