In the mathematical field of graph theory, the complement or inverse of a graph is a graph on the same vertices such that two distinct vertices of are adjacent if and only if they are not adjacent in . That is, to generate the complement of a graph, one fills in all the missing edges required to form a complete graph, and removes all the edges that were previously there. The complement is not the set complement of the graph; only the edges are complemented. Definition Let be a simple graph and let consist of all 2-element subsets of . Then is the complement of , where is the relative complement of in . 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 in place of the set in the formula above. In terms of the adjacency matrix A of the graph, if Q is the adjacency matrix of the complete graph of the same number of vertices (i.e. all entries are unity except the diagonal entries which are zero), then the adjacency matrix of the complement of A is Q-A. The complement is not defined for multigraphs. In graphs that allow self-loops (but not multiple adjacencies) the complement of may be defined by adding a self-loop to every vertex that does not have one in , and otherwise using the same formula as above. This operation is, however, different from the one for simple graphs, since applying it to a graph with no self-loops would result in a graph with self-loops on all vertices. Applications and examples Several graph-theoretic concepts are related to each other via complementation: The complement of an edgeless graph is a complete graph and vice versa. Any induced subgraph of the complement graph of a graph is the complement of the corresponding induced subgraph in . An independent set in a graph is a clique in the complement graph and vice versa. This is a special case of the previous two properties, as an independent set is an edgeless induced subgraph and a clique is a complete induced subgraph. The automorphism group of a graph is the automorphism group of its complement. The complement of every triangle-free graph is a claw-free graph, although the reverse is not true. Self-complementary graphs and graph classes A