Graph Theory: Complement of a Graph

AI Thread 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 'Trigonometry problem of interest'

Seemingly by some mathematical coincidence, a hexagon of sides 2,2,7,7, 11, and 11 can be inscribed in a circle of radius 7. The other day I saw a math problem on line, which they said came from a Polish Olympiad, where you compute the length x of the 3rd side which is the same as the radius, so that the sides of length 2,x, and 11 are inscribed on the arc of a semi-circle. The law of cosines applied twice gives the answer for x of exactly 7, but the arithmetic is so complex that the...
View full post »

Similar threads

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

Hot Threads

Recent Insights

Back
Top