Register to reply

Combinatorics/graph theory: Digraphs and cycles

by KroneckerDelta
Tags: cycles, digraphs, theory
Share this thread:
KroneckerDelta
#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
Bees able to spot which flowers offer best rewards before landing
Classic Lewis Carroll character inspires new ecological model
When cooperation counts: Researchers find sperm benefit from grouping together in mice

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