Register to reply

Combinatorics/graph theory: Digraphs and cycles

by KroneckerDelta
Tags: cycles, digraphs, theory
Share this thread:
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
FIXD tells car drivers via smartphone what is wrong
Team pioneers strategy for creating new materials
Team defines new biodiversity metric

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... Fun, Photos & Games 1
Number of cycles in a graph ? Programming & Computer Science 0