Graph theory - complete subgraphs

Click For Summary
SUMMARY

The discussion centers on proving that in a graph G of order n (where n ≥ 4) with every vertex v having a degree of (2n+1)/3, every edge in G is part of a complete subgraph of order 4. The user has established this for complete graphs through induction but seeks assistance in extending the proof to non-complete graphs. The degree condition (2n+1)/3 is crucial as it indicates a specific structural property of the graph that facilitates the existence of complete subgraphs.

PREREQUISITES
  • Understanding of graph theory concepts, particularly subgraphs and vertex degrees.
  • Familiarity with complete graphs and their properties.
  • Knowledge of mathematical induction as a proof technique.
  • Basic comprehension of graph orders and their implications in graph structure.
NEXT STEPS
  • Research the properties of complete subgraphs in graph theory.
  • Study the implications of vertex degree conditions in graph connectivity.
  • Explore advanced proof techniques in graph theory beyond induction.
  • Investigate the significance of the degree formula (2n+1)/3 in relation to graph properties.
USEFUL FOR

Mathematicians, computer scientists, and students studying graph theory, particularly those interested in subgraph properties and proof techniques.

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?
 

Similar threads

Graduate When can transitivity emerge from cycle-suppressing dynamics?
  • · Replies 1 ·
Replies
1
Views
483
MHB Is HSC NP-Complete in Graph Theory?
  • · Replies 1 ·
Replies
1
Views
2K
MHB Graph: showing that diameter is greater than average pairwise distance
  • · Replies 4 ·
Replies
4
Views
4K
MHB Minimum Degree of a Random Graph (Probabilistic Method)
  • · Replies 1 ·
Replies
1
Views
2K
MHB Are Events in Random Graphs from G(n, 1/2) Independent?
  • · Replies 1 ·
Replies
1
Views
2K
Graduate Is F a Subgraph of Every Spanning Tree of G If It Contains No Cycles?
  • · Replies 15 ·
Replies
15
Views
5K
Graduate Concrete examples of randomness in math vs. probability theory
  • · Replies 11 ·
Replies
11
Views
3K
Undergrad Understanding a Graph Theory Proof
  • · Replies 3 ·
Replies
3
Views
1K
MHB Some basic questions on Graph theory
  • · Replies 2 ·
Replies
2
Views
2K
MHB Problem on Graph Theory and Algorithms
  • · Replies 2 ·
Replies
2
Views
3K