Graph theory - complete subgraphs

In summary, a complete subgraph in graph theory is a subset of vertices within a larger graph where all vertices are connected to each other by an edge. They are significant in identifying patterns and have applications in various fields. The number of edges in a complete subgraph is equal to the number of vertices squared, minus the number of vertices. Complete subgraphs cannot have more than one edge between two vertices, and they are essentially equivalent to cliques in graph theory.
  • #1
Gh0stZA
25
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
  • #2
Sorry to bump, any help please?
 

1. What is a complete subgraph in graph theory?

A complete subgraph in graph theory refers to a subset of vertices within a larger graph, where all of the vertices are connected to each other by an edge. This means that within the subset, every vertex is connected to every other vertex, making it a fully connected subgraph.

2. What is the significance of complete subgraphs in graph theory?

Complete subgraphs are important in graph theory because they allow for the identification of specific patterns or structures within a larger graph. They also have applications in various fields, including computer science, social networks, and biology.

3. How many edges are in a complete subgraph?

The number of edges in a complete subgraph is equal to the number of vertices squared, minus the number of vertices. In other words, if a complete subgraph has n vertices, it will have n(n-1)/2 edges.

4. Can a complete subgraph have more than one edge between two vertices?

No, a complete subgraph cannot have more than one edge between two vertices. This is because the definition of a complete subgraph states that all vertices must be connected to each other by an edge, and multiple edges between two vertices would violate this condition.

5. How do complete subgraphs relate to cliques in graph theory?

In graph theory, a clique is a subset of vertices within a larger graph where every vertex is connected to every other vertex. This is the same definition as a complete subgraph, so complete subgraphs and cliques are essentially equivalent concepts.

Similar threads

MHB Chordal graphs and perfect elimination orderings
    • Set Theory, Logic, Probability, Statistics
Replies
1
Views
1K
MHB Graph: showing that diameter is greater than average pairwise distance
    • Set Theory, Logic, Probability, Statistics
Replies
4
Views
3K
MHB Minimum Degree of a Random Graph (Probabilistic Method)
    • Set Theory, Logic, Probability, Statistics
Replies
1
Views
1K
MHB Are Events in Random Graphs from G(n, 1/2) Independent?
    • Set Theory, Logic, Probability, Statistics
Replies
1
Views
1K
MHB Show that HSC is NP-complete
    • Set Theory, Logic, Probability, Statistics
Replies
1
Views
1K
MHB Understanding Two Graph Theory Problems
    • Set Theory, Logic, Probability, Statistics
Replies
2
Views
2K
I Understanding a Graph Theory Proof
    • General Math
Replies
3
Views
680
Is F a Subgraph of Every Spanning Tree of G If It Contains No Cycles?
    • Set Theory, Logic, Probability, Statistics
Replies
15
Views
4K
Prove the decomposition of a graph w/ even edges produce a 2-path set
    • Calculus and Beyond Homework Help
Replies
1
Views
1K
MHB Ice Cream : NP-complete problem
    • Set Theory, Logic, Probability, Statistics
Replies
6
Views
2K

Hot Threads

Recent Insights

Back
Top