I have the following problem, suppose we have a graph G of n elements, with the property that if we add one missing vertex v, we will get a complete subgraph with s elements K_s of G, in which v belongs to G'. In other words every subgraph of s elements of G is almost a complete graph except for at most one missing vertex. (s is fixed btw).(adsbygoogle = window.adsbygoogle || []).push({});

The problem is to prove that |E(G)| >= C(n,2) - C(n-s+2,2), |E(G)| is the number of edges of G. C(n,k) is the binomial coeficient.

I am not sure if this is the appropiate forum for this kind of questions, but couldn't find any adequate subforum.

Any help is appreciated.

**Physics Forums - The Fusion of Science and Community**

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

# Interesting graph theory problem

Can you offer guidance or do you also need help?

Draft saved
Draft deleted

Loading...

Similar Threads - Interesting graph theory | Date |
---|---|

B Basic Graphing | Mar 9, 2018 |

I Two interesting equalities | Aug 9, 2017 |

I Interesting question: why is ln(-1) in polar form...? | Mar 30, 2017 |

Insights Using the Fourier Series To Find Some Interesting Sums - Comments | Dec 22, 2016 |

I Boas 1.13 Compound interest/geometric series | Sep 17, 2016 |

**Physics Forums - The Fusion of Science and Community**