Hi everyone.(adsbygoogle = window.adsbygoogle || []).push({});

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? If we have a graph G of order n >= 4, and every vertex v in G has degree (2n+1)/3, prove that every edge in G is part of a complete subgraph of order 4.

**Physics Forums | Science Articles, Homework Help, Discussion**

Dismiss Notice

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Graph theory - complete subgraphs

Loading...

Similar Threads for Graph theory complete |
---|

A About the “Axiom of Dependent Choice” |

B What is the usefulness of formal logic theory? |

I Countability of ℚ |

I Representing Tiling and Packing Solutions |

**Physics Forums | Science Articles, Homework Help, Discussion**