Understanding a Graph Theory Proof

Click For Summary

Discussion Overview

The discussion revolves around a proof concerning graph theory, specifically addressing the properties of a simple graph with 6 vertices and the existence of a subgraph isomorphic to ##K_3## in either the graph or its complement. The scope includes theoretical exploration and mathematical reasoning.

Discussion Character

  • Exploratory, Mathematical reasoning

Main Points Raised

  • One participant asserts that if a simple graph G has 6 vertices, then either G or its complement must have a vertex with degree at least 3.
  • Another participant suggests that if a chosen vertex has a degree smaller than 3, its complement's degree should be considered to further the proof.
  • A later reply proposes a generalization, questioning whether it can be stated that G or its complement must have a vertex with degree at least ##\lfloor v/2 \rfloor##, where v is the number of vertices.
  • One participant confirms the generalization proposed in the last point.

Areas of Agreement / Disagreement

Participants express agreement on the initial assertion regarding the degree of vertices in G or its complement, but the generalization remains a point of exploration without explicit consensus.

Contextual Notes

The discussion does not resolve the implications of the generalization or the specific conditions under which the initial claim holds true.

Who May Find This Useful

Individuals interested in graph theory, particularly those exploring properties of graphs and their complements, may find this discussion relevant.

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   Reactions: 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##?
 

Similar threads

Undergrad Question regarding degrees of a graph and its biconnected components
  • · Replies 34 ·
2
Replies
34
Views
6K
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 Finding the dependence of maximum vertex degree on k-colorability
  • · Replies 1 ·
Replies
1
Views
2K
Undergrad Graph Theory: (proof)conditions for Euler Circuit in Digraph
  • · Replies 1 ·
Replies
1
Views
4K
Insights Fermat's Last Theorem
  • · Replies 105 ·
4
Replies
105
Views
10K
Graduate How Do You Prove Minimum Vertex Degree in Graph Theory?
  • · Replies 1 ·
Replies
1
Views
2K