Re: Please help Graph Theory
- From: "Chip Eastham" <hardmath@xxxxxxxxx>
- Date: 29 Jan 2006 19:43:20 -0800
Robert Israel wrote:
> In article <1138570992.735299.319590@xxxxxxxxxxxxxxxxxxxxxxxxxxxx>,
> <charleshowardmath@xxxxxxxxx> wrote:
> >Could someone help me understand why this is true:
> > Every graph with average degree d contains a bipartite subgraph of
> >average degree at least d/2.
> >
> >Thanks Charles
>
> Hint: suppose we randomly label the vertices "a" and "b". What is
> the expected number of edges whose vertices have different labels?
>
> Robert Israel israel@xxxxxxxxxxx
> Department of Mathematics http://www.math.ubc.ca/~israel
> University of British Columbia Vancouver, BC, Canada
Extracting a deterministic conclusion by a probabilistic argument.
Very nice!. One actually gets average degree > d/2, if "a" and "b"
subsets are chosen of nearly equal numbers in bipartite subgraph.
regards, chip
.
- References:
- Please help Graph Theory
- From: charleshowardmath
- Re: Please help Graph Theory
- From: Robert Israel
- Please help Graph Theory
- Prev by Date: Re: Compactness in Hilbert spaces
- Next by Date: Re: Is my calculus right?
- Previous by thread: Re: Please help Graph Theory
- Next by thread: Re: Is my calculus right?
- Index(es):
Relevant Pages
|
