Undergrad Understanding a Graph Theory Proof

Click For Summary
If a simple graph G has 6 vertices, either G or its complement must contain a subgraph isomorphic to K3. The proof starts by establishing that at least one of these graphs has a vertex with a degree of at least 3. If a chosen vertex has a degree less than 3, its complement must have a degree of at least 3. This reasoning leads to the conclusion that the result can generalize, suggesting that for any graph with v vertices, either the graph or its complement will have a vertex with a degree of at least ⌊v/2⌋. The discussion emphasizes the importance of vertex degrees in graph theory proofs.
Mr Davis 97
Messages
1,461
Reaction score
44
Prove that if a simple graph G has 6 vertices then G or its complement has a subgraph isomorphic to ##K_3##.

The proof begins by noting that is must be the case that G or its complement as a vertex with degree at least 3. Why is this the case?
 
Mathematics news on Phys.org
Pick a random vertex. If its degree is 3 or more you are done. If its degree is smaller, what is the degree of the vertex for the complement?
 
  • Like
Likes Mr Davis 97
mfb said:
Pick a random vertex. If its degree is 3 or more you are done. If its degree is smaller, what is the degree of the vertex for the complement?
I got it now. How would this result generalize? Would it be correct to say that G or its complement must have a vertex with degree at least ##\lfloor v/2 \rfloor##?
 

Thread 'Area of Overlapping Squares'

Here is a little puzzle from the book 100 Geometric Games by Pierre Berloquin. The side of a small square is one meter long and the side of a larger square one and a half meters long. One vertex of the large square is at the center of the small square. The side of the large square cuts two sides of the small square into one- third parts and two-thirds parts. What is the area where the squares overlap?
View full post »

Similar threads

Undergrad Question regarding degrees of a graph and its biconnected components
  • · Replies 34 ·
2
Replies
34
Views
5K
Undergrad Prove that a given graph contains a cycle using induction (Graph Theory)
  • · Replies 7 ·
Replies
7
Views
3K
Undergrad Finding if a subgraph of a minimal non-planar graph is maximal planar
  • · Replies 1 ·
Replies
1
Views
2K
Graduate Every graph GG containing a cycle satisfies g(G)≤2d+1
  • · Replies 10 ·
Replies
10
Views
3K
Undergrad Finding the chromatic number of a graph with biconnected components
  • · Replies 1 ·
Replies
1
Views
2K
Undergrad Classify the isomorphism of a graph
  • · Replies 3 ·
Replies
3
Views
2K
Undergrad Graph Theory: (proof)conditions for Euler Circuit in Digraph
  • · Replies 1 ·
Replies
1
Views
3K
Insights Fermat's Last Theorem
  • · Replies 105 ·
4
Replies
105
Views
8K
How Do You Prove Minimum Vertex Degree in Graph Theory?
  • · Replies 1 ·
Replies
1
Views
2K
Prove the decomposition of a graph w/ even edges produce a 2-path set
  • · Replies 1 ·
Replies
1
Views
2K