Combinatorics/graph theory: Digraphs and cycles

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

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
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