Graph theory - complete subgraphs

Gh0stZA
Messages
25
Reaction score
0
Hi everyone.

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.
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?
 
Physics news on Phys.org
Sorry to bump, any help please?
 

Thread 'Roulette wheel physics and probability'

Hi all, I've been a roulette player for more than 10 years (although I took time off here and there) and it's only now that I'm trying to understand the physics of the game. Basically my strategy in roulette is to divide the wheel roughly into two halves (let's call them A and B). My theory is that in roulette there will invariably be variance. In other words, if A comes up 5 times in a row, B will be due to come up soon. However I have been proven wrong many times, and I have seen some...
View full post »
Thread 'Detail of Diagonalization Lemma'

Thread 'Detail of Diagonalization Lemma'

The following is more or less taken from page 6 of C. Smorynski's "Self-Reference and Modal Logic". (Springer, 1985) (I couldn't get raised brackets to indicate codification (Gödel numbering), so I use a box. The overline is assigning a name. The detail I would like clarification on is in the second step in the last line, where we have an m-overlined, and we substitute the expression for m. Are we saying that the name of a coded term is the same as the coded term? Thanks in advance.
View full post »

Similar threads

MHB Is HSC NP-Complete in Graph Theory?
Replies
1
Views
2K
MHB Minimum Degree of a Random Graph (Probabilistic Method)
Replies
1
Views
2K
MHB Graph: showing that diameter is greater than average pairwise distance
Replies
4
Views
3K
MHB Are Events in Random Graphs from G(n, 1/2) Independent?
Replies
1
Views
2K
MHB Understanding Two Graph Theory Problems
Replies
2
Views
2K
Is F a Subgraph of Every Spanning Tree of G If It Contains No Cycles?
Replies
15
Views
5K
I Understanding a Graph Theory Proof
Replies
3
Views
921
MHB Some basic questions on Graph theory
Replies
2
Views
2K
MHB Strong induction hypothesis for statement about connected graphs
Replies
4
Views
2K
MHB Ice Cream : NP-complete problem
Replies
6
Views
2K

Hot Threads

Recent Insights

Back
Top