Re: Please help Graph Theory
- From: israel@xxxxxxxxxxx (Robert Israel)
- Date: 29 Jan 2006 22:44:40 GMT
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
.
- Follow-Ups:
- Re: Please help Graph Theory
- From: Chip Eastham
- Re: Please help Graph Theory
- References:
- Please help Graph Theory
- From: charleshowardmath
- Please help Graph Theory
- Prev by Date: Re: Is my calculus right?
- Next by Date: Re: Show this matrix is not diagonalizable
- Previous by thread: Please help Graph Theory
- Next by thread: Re: Please help Graph Theory
- Index(es):
Relevant Pages
|
