In a non-bipartite graph ( without triangles ) on n-nodes , prove the existence of a node with degree at most 2n/5.

Note: Its easy to see that there must be a node with degree at most n/2.

Printable View

- Oct 25th 2009, 06:08 AMDeRSeDProof of 2n/5 degree node in a NBP graph
In a non-bipartite graph ( without triangles ) on n-nodes , prove the existence of a node with degree at most 2n/5.

Note: Its easy to see that there must be a node with degree at most n/2.