Graph theory - complete subgraphs

AI Thread Summary
In a graph G with order n ≥ 4, if every vertex has a degree of (2n+1)/3, it can be shown that every edge is part of a complete subgraph of order 4. The degree condition suggests that vertices are sufficiently connected, which is critical for forming complete subgraphs. The discussion highlights the challenge of proving this for non-complete graphs, as the properties of the degree must be leveraged effectively. Understanding the implications of the degree (2n+1)/3 is essential for identifying the necessary structural properties of the graph. The inquiry seeks assistance in formalizing the proof and exploring the significance of the degree condition.
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 'Formal derivation of statement from Peano Arithmetic system'

I was reading a Bachelor thesis on Peano Arithmetic (PA). PA has the following axioms (not including the induction schema): $$\begin{align} & (A1) ~~~~ \forall x \neg (x + 1 = 0) \nonumber \\ & (A2) ~~~~ \forall xy (x + 1 =y + 1 \to x = y) \nonumber \\ & (A3) ~~~~ \forall x (x + 0 = x) \nonumber \\ & (A4) ~~~~ \forall xy (x + (y +1) = (x + y ) + 1) \nonumber \\ & (A5) ~~~~ \forall x (x \cdot 0 = 0) \nonumber \\ & (A6) ~~~~ \forall xy (x \cdot (y + 1) = (x \cdot y) + x) \nonumber...
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
945
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