Graph Theory: Complement of a Graph

Click For Summary
A complete graph G has edges between every pair of its n vertices, while its complement G' contains edges that are not present in G. For a complete graph like K_3, its complement has no edges, making it an empty graph. The discussion raises the question of whether both G and G' can be complete simultaneously. It is clarified that only trivial cases, such as K_0 and K_1, allow for both G and G' to be complete. The conclusion emphasizes that for larger graphs, G and G' cannot both be complete.
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 K_3, 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?
 

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 Understanding a Graph Theory Proof
  • · Replies 3 ·
Replies
3
Views
977
Undergrad Find Smallest Subtree of G w/ Nodes from S
  • · Replies 5 ·
Replies
5
Views
2K
High School Just for fun: Cubic Graph Plot
  • · Replies 1 ·
Replies
1
Views
1K
Undergrad Finding if a subgraph of a minimal non-planar graph is maximal planar
  • · Replies 1 ·
Replies
1
Views
2K
Undergrad Correlation vs causality implied by a graph
  • · Replies 45 ·
2
Replies
45
Views
4K
Undergrad Adding 'z' to 2D graph equation
  • · Replies 3 ·
Replies
3
Views
2K
Undergrad Traffic simulation : directed graph including specific rules
  • · Replies 5 ·
Replies
5
Views
2K
Undergrad Prove that a given graph contains a cycle using induction (Graph Theory)
  • · Replies 7 ·
Replies
7
Views
3K
MHB 7.t.27 write eq for a sinusiol graph
  • · Replies 2 ·
Replies
2
Views
1K
High School Looking for free graphing calculator for two-variable inequality
  • · Replies 4 ·
Replies
4
Views
2K