Interesting graph theory problem

  • #1
alejopelaez
1
0
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).

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.
 

Answers and Replies

  • #2
fresh_42
Mentor
Insights Author
2021 Award
17,197
17,147
You have to show that you already must have a certain number of edges for otherwise the condition cannot hold. I would start with small s and an example to see how a path to a proof could look like.
 

Suggested for: Interesting graph theory problem

  • Last Post
Replies
3
Views
2K
  • Last Post
Replies
3
Views
5K
  • Last Post
Replies
10
Views
2K
  • Last Post
Replies
3
Views
2K
  • Last Post
Replies
5
Views
3K
  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
4
Views
8K
  • Last Post
Replies
18
Views
3K
  • Last Post
Replies
9
Views
2K
  • Last Post
Replies
3
Views
2K
Top