Talk:Complement graph

First and second bullets in examples

The first and the second bullet in the examples are saying the same thing using different words. We should remove the one or the other. Leaving them like they are now would be confusing. Vitalij zad (talk) 09:54, 1 September 2012 (UTC)[reply]

I think they're different enough to stay. One is about what happens when the whole graph is edgeless or complete; the other is about what happens to subgraphs within the graph. —David Eppstein (talk) 15:50, 1 September 2012 (UTC)[reply]

I agree that they're different enough to stay, all the more so as: an independent subset

S

of

G

may have edges between its vertices & those of

V \ S

, & a clique

S

of

G

may have not all edges between its vertices & those of

V \ S

. —JavBol (talk) 16:52, 20 January 2026 (UTC)[reply]

Simple graphs only?

Is it the case that the concept of a complement graph makes sense for simple graphs only?

It's clear that the complement is a simple graph, because the complement never connects a vertex to itself, nor does it feature two or more edges between the same pair of vertices.

Must the input graph to the complement operation also be simple?

In terms of an adjacency matrix representation, must the input matrix just have 1's and 0's, with an all zero diagonal?

If so, we can also describe the complement in terms of the adjacency matrix representation:

the diagonal zeros stay zero
all other entries flip from 0 to 1 and vice versa

216.31.219.19 (talk) 19:42, 18 December 2013 (UTC)[reply]

I think in order to have some other nice properties (in particular that the complement of a complement is the original graph) it's necessary to assume that the input graph is simple. —David Eppstein (talk) 19:50, 18 December 2013 (UTC)[reply]

Definition of complement of simple directed graph

In Complement graph#Definitions, in the following passage:

Let $G = (V, E)$ be a simple graph and let $K$ consist of all 2-element subsets of $V$ . Then $H = (V, K \ E)$ is the complement of $G$ , where $K \ E$ is the relative complement of $E$ in $K$ . For directed graphs, the complement can be defined in the same way, as a directed graph on the same vertex set, using the set of all 2-element ordered pairs of $V$ in place of the set $K$ in the formula above.,

the 2nd part should be something like:

Let $G = (V, D)$ be a simple directed graph and let $T$ consist of all pairs of ordered pairs of elements of $V$ of the form ${(u, v), (v, u)$ }. Then the simple directed graph $H = (V, T \ D)$ is the complement of $G$ . Note: if no arrows or both arrows $(u, v)$ and $(v, u)$ are between $u$ and $v$ in $G$ , then both arrows $(u, v)$ and $(v, u)$ or no arrows are between $u$ and $v$ in $H$ , and vice versa.;

shouldn't it? —JavBol (talk) 23:54, 21 January 2026 (UTC)[reply]

I don't understand your notation. For a directed graph (V,A), the set of arcs A is a set of ordered pairs, not pairs of ordered pairs. The complement is just (V,P\A) where P is the set of all ordered pairs of distinct vertices in V. —David Eppstein (talk) 00:16, 22 January 2026 (UTC)[reply]

My proposal was to proceed pair of vertices by pair of vertices; I should have phrased it in a way like:
Let $G = (V, A)$ be a simple directed graph, let $T$ be the ordered set of all pairs of ordered pairs of vertices in $V$ of the form ${(u, v), (v, u)$ }, & let $D$ be the ordered set of all « Ø, or ${(u, v)$ }, or ${(v, u)$ }, or ${(u, v), (v, u)$ } » that are in $A$ . Then the simple directed graph $H = (V, T \ D)$ is the complement of $G$ .
But yes, it is uselessly complicated… Sorry!

Could I rephrase the whole passage to:

Let $G = (V, E)$ be a simple graph and let $P$ consist of all pairs of distinct vertices in $V$ . Then the simple graph $H = (V, P \ E)$ is the complement of $G$ , where $P \ E$ is the relative complement of $E$ in $P$ .

Let $G = (V, A)$ be a simple directed graph and let $O$ consist of all ordered pairs of distinct vertices in $V$ . Then the simple directed graph $H = (V, O \ A)$ is the complement of $G$ .,

please? —JavBol (talk) 16:25, 22 January 2026 (UTC)[reply]

What do you think is wrong with the current wording? —David Eppstein (talk) 19:22, 22 January 2026 (UTC)[reply]

Thank you for your 3 answers.

Except for the lack of separation between the 1st & 2nd parts, I don't think anything is really wrong with the current phrasing. But I find my latest proposal clearer & more explicit, & thus more appropriate before perhaps giving the (correct?) adjacency-matrix formula for a simple directed graph:

mat(H) = mat(Ω) - mat(G)

, or

\mathrm {mat} ({\overline {G}})=\mathrm {mat} (\varOmega )-\mathrm {mat} (G),

where

Ω

is the complete simple directed graph on the same number of vertices, &

mat(G)

is not necessarily symmetric. —JavBol (talk) 00:02, 23 January 2026 (UTC)[reply]

Definition of complement of graph if self-loops are allowed

The following sentence,
In graphs that allow self-loops (but not multiple adjacencies), the complement of G may be defined by adding a self-loop to every vertex that does not have one in G, and otherwise using the same formula as above.,
should be something like (underlinings just show my suggested changes):
For a graph G that allows self-loops (but not multiple adjacencies), the complement of G may be defined by adding a self-loop to every vertex that does not have one in G, removing its self-loop from every vertex that has one in G, and otherwise using the same formula as above.;
shouldn't it? —JavBol (talk) 21:41, 19 January 2026 (UTC)[reply]

No. It has to be about what class of graphs you are complementing, not about a single graph. Otherwise if you complemented a graph without loops you would have no idea whether you should add loops or not, —David Eppstein (talk) 19:20, 22 January 2026 (UTC)[reply]

Then, what about the following phrasing (underlinings just show my suggested changes):
In graphs that allow self-loops (but not multiple adjacencies), the complement of a graph G may be defined by adding a self-loop to every vertex that does not have one in G, removing its self-loop from every vertex that has one in G, and otherwise using the same formula as above.,
please? —JavBol (talk) 00:02, 23 January 2026 (UTC)[reply]

Unclear sentence in #«Self-complementary graphs and graph classes»

In the following sentence,
Another, self-complementary definition is that they are the graphs with no induced subgraph in the form of a four-vertex path.,
(1) the 1st comma seems to require a further comma (doesn't it?);
(2) is «they» referring to self-complementary graphs or to cographs? —JavBol (talk) 22:13, 19 January 2026 (UTC)[reply]

Cographs. There is no grammatical way of interpreting this as referring to self-complementary graphs. —David Eppstein (talk) 22:20, 19 January 2026 (UTC)[reply]

Thanks; so, does the same sentence mean:

Another definition, but related to self-complementarity, is that a cograph is a graph with no four-vertex path as an induced subgraph.,

please? —JavBol (talk) 21:52, 20 January 2026 (UTC)[reply]

The definition is not merely vaguely "related to self-complementarity". It is a self-complementary definition. If you complement the things in the definition you get the same definition. Your rewording loses that idea and is much less crisp. —David Eppstein (talk) 18:45, 22 January 2026 (UTC)[reply]

Ah, something like:

«~~The complement of~~ a cograph is a graph with no induced subgraph in the form of ~~the complement of~~ a four-vertex path.»,

right? —JavBol (talk) 00:02, 23 January 2026 (UTC)[reply]

The point is that when you complement the set of graphs being defined and adjust the definition (what you get with your text before you struck out some of it), and when you then see "the complement of a four-vertex path" is the same as "a four-vertex path", it should become very obvious to you that the cographs are closed under complementation. —David Eppstein (talk) 02:18, 23 January 2026 (UTC)[reply]