Re: Graph Theory question
- From: mareg@xxxxxxxxxxxxxxxxxxxxxxxx ()
- Date: Mon, 30 Jan 2006 18:53:26 +0000 (UTC)
In article <1138590457.662357.166560@xxxxxxxxxxxxxxxxxxxxxxxxxxxx>,
charleshowardmath@xxxxxxxxx writes:
>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.
>
You could partition the vertices into two sets A, B so as to maximize the
number of edges going between A and B. Then each vertex in A would have
at least as many edges going to B as to A, and similarly for vertices in B.
Derek Holt.
.
- References:
- Graph Theory question
- From: charleshowardmath
- Graph Theory question
- Prev by Date: Re: Significance of "Relativizations of the P =? NP Question"
- Next by Date: Re: dynamic programming on a tree
- Previous by thread: Re: Graph Theory question
- Index(es):
Relevant Pages
|
