Graph Theory: Complement of a Graph

jack_bauer · Nov 17, 2009

I'm wondering, is it possible a graph G and its complement G' to be complete?

statdad · Nov 17, 2009

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.

letmeknow · Nov 17, 2009

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?

CRGreathouse · Nov 17, 2009

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.

roadrunner · Oct 13, 2010

i think you mean G union G' to be complete?

Graph Theory: Complement of a Graph

High School Ant on a stretchy rope puzzle

High School Potato paradox

Geometric Game: Fun With Matches (Safe!)

Undergrad Three Circle Problem

High School Three Squares Problem

Insights Revisiting the Velocity-Time Function

Insights Remote Operated Gate Control System

Insights AI Enriched Problem Solving

Insights Thinking Outside The Box Versus Knowing What’s In The Box

Insights Why Entangled Photon-Polarization Qubits Violate Bell’s Inequality

Insights Quantum Entanglement is a Kinematic Fact, not a Dynamical Effect

Graph Theory: Complement of a Graph

Similar threads