Aka. inverse. For a simple graph G = ( V , E ) G=(V,E) G = ( V , E ) G c ( V , E c ) G^c(V,E^c) G c ( V , E c ) E c = { { u , v } ; ∀ u , v ∈ V ∧ u ≠ v ∧ { u , v } ∉ E } E^c = \set{ \set{u,v}; \forall u,v \in V \land u \neq v \land \set{u,v} \not\in E } E c = { { u , v } ; ∀ u , v ∈ V ∧ u = v ∧ { u , v } ∈ E } iff they are not adjacent in G G G
Undefined for multigraphs.
( G c ) c = G (G^c)^c = G ( G c ) c = G
Proof Hint
Suppose G = ( V , E ) G=(V,E) G = ( V , E )
G c ( V , E c ) G^c(V,E^c) G c ( V , E c ) For ( G c ) c (G^c)^c ( G c ) c ( E c ) c = E (E^c)^c = E ( E c ) c = E
OR:
Suppose { u , v } ∈ E \set{u,v} \in E { u , v } ∈ E
E c E^c E c Hence it must exist in ( E c ) c (E^c)^c ( E c ) c
Prove the other way as well
For any graph G G G n n n G c G^c G c K n K_n K n
Proof Hint
Suppose G = ( V , E ) G=(V,E) G = ( V , E ) n n n
G c ( V , E c ) G^c(V,E^c) G c ( V , E c ) For all pair of vertices u u u v v v
If an edge exists between then in G G G G ∪ G c G\cup G^c G ∪ G c
If not, it exists in G c G^c G c G ∪ G c G\cup G^c G ∪ G c
G ∪ G c G\cup G^c G ∪ G c K n K_n K n
Self-Complementary Graph
A graph satisfying G = G c G = G^c G = G c
Has n ( n − 1 ) 4 \frac{n(n-1)}{4} 4 n ( n − 1 )
Proof Hint
G ∪ G c = K n G\cup G^c = K_n G ∪ G c = K n n ( n − 1 ) 2 \frac{n(n-1)}{2} 2 n ( n − 1 ) As G = G c G = G^c G = G c
Hence ∣ E ( G ) ∣ = n ( n − 1 ) 4 |E(G)| = \frac{n(n-1)}{4} ∣ E ( G ) ∣ = 4 n ( n − 1 )
