Re: Graph Theory question
- From: "Googmeister" <googmeister@xxxxxxxxx>
- Date: 30 Jan 2006 06:01:35 -0800
John Gabbriel wrote:
> charleshowardmath@xxxxxxxxx wrote:
> > Could someone tell me why this is true:
> > Every graph with average degree d contains a bipartite subgraph of
> > average degree at least d/2.
> >
> >
> > Thanks Charles
>
> Is this homework?
Hint: use the probabilistic method.
.
- References:
- Graph Theory question
- From: charleshowardmath
- Re: Graph Theory question
- From: John Gabbriel
- Graph Theory question
- Prev by Date: Re: Graph Theory question
- Next by Date: Re: Significance of "Relativizations of the P =? NP Question"
- Previous by thread: Re: Graph Theory question
- Next by thread: Re: Graph Theory question
- Index(es):
Relevant Pages
|
