Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Graph theory - complete subgraphs

  1. Feb 23, 2012 #1
    Hi everyone.

    I know this holds for complete graphs, I've proved that by induction. But how can I prove it for graphs which aren't complete? And what is the significance of (2n+1)/3? If a vertex has that degree, does it have some property I should immediately spot?
  2. jcsd
  3. Feb 24, 2012 #2
    Sorry to bump, any help please?
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook