Graph Theory: Complement of a Graph

Click For Summary

Discussion Overview

The discussion revolves around the properties of a graph and its complement in graph theory, specifically whether both a graph G and its complement G' can be complete. The scope includes theoretical exploration and conceptual clarification.

Discussion Character

  • Exploratory, Conceptual clarification, Debate/contested

Main Points Raised

  • One participant questions if it is possible for a graph G and its complement G' to both be complete.
  • Another participant suggests examining the complete graph K_3 and its complement to draw conclusions about the general case.
  • A third participant explains the definition of a complete graph and describes how the complement is constructed, noting that if G is complete, there are no edges missing.
  • A later reply confirms that for the cases of K_0 and K_1, both G and G' can be complete.
  • One participant proposes that the question may actually refer to the union of G and G' being complete.

Areas of Agreement / Disagreement

Participants express differing views on the possibility of both G and G' being complete, with some supporting the idea for specific cases while others suggest a different interpretation of the question. The discussion remains unresolved regarding the general case.

Contextual Notes

The discussion does not fully explore the implications of the definitions of complete graphs and their complements, nor does it clarify the conditions under which the claims are made.

jack_bauer
Messages
10
Reaction score
0
I'm wondering, is it possible a graph G and its complement G' to be complete?
 
Mathematics news on Phys.org
Start with the complete graph [tex]K_3[/tex], and find its complement. What do you notice? Think about the definition of the complement of a graph and think about what would happen in general.
 
A complete graph G on n vertices is a graph that has an edge between any two vertices, no matter which two you pick. The complement of G is a graph of n vertices and is constructed by drawing the n vertices on the paper and then filling in the edges that are not present in G. Which edges are missing in G if G is complete?
 
jack_bauer said:
I'm wondering, is it possible a graph G and its complement G' to be complete?

Sure, for K_0 and K_1.
 
i think you mean G union G' to be complete?
 

Similar threads

Undergrad Understanding a Graph Theory Proof
  • · Replies 3 ·
Replies
3
Views
1K
Undergrad Find Smallest Subtree of G w/ Nodes from S
  • · Replies 5 ·
Replies
5
Views
2K
Undergrad Finding if a subgraph of a minimal non-planar graph is maximal planar
  • · Replies 1 ·
Replies
1
Views
2K
High School Just for fun: Cubic Graph Plot
  • · Replies 1 ·
Replies
1
Views
1K
Undergrad Adding 'z' to 2D graph equation
  • · Replies 3 ·
Replies
3
Views
2K
Undergrad Prove that a given graph contains a cycle using induction (Graph Theory)
  • · Replies 7 ·
Replies
7
Views
3K
Undergrad Traffic simulation : directed graph including specific rules
  • · Replies 5 ·
Replies
5
Views
2K
Undergrad The number of intersection graphs of ##n## convex sets in the plane
  • · Replies 2 ·
Replies
2
Views
1K
Undergrad Find Two Equal Length Paths in a Tree Graph
  • · Replies 4 ·
Replies
4
Views
2K
Undergrad Explanation for parity difference for # of simple graphs
  • · Replies 4 ·
Replies
4
Views
1K