Talk:Complement graph

This article is rated C-class on Wikipedia's content assessment scale. It is of interest to the following WikiProjects:

Mathematics Mid‑priority This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.MathematicsWikipedia:WikiProject MathematicsTemplate:WikiProject Mathematicsmathematics Mid This article has been rated as Mid-priority on the project's priority scale.

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

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

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 ${\displaystyle \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

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

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