Question

complement of a graph let n=3 it is complete graph what is meant by its complement ?

Comments

Complement of a graph is like having same vertices .Edges will differ i.e You have to fill all the edges in a graph which would be there if the graph is complete i.e
Complement graph of A + graph of A=Complete Graph of A[Same vertices but edges differ].

---

For n=3, if the graph is complete then the complement of that graph is null graph(with no edges.).

Answer 1

In graph theory, the complement or inverse of a graph G is a graph H on the same vertices such that two distinct vertices of H are adjacent if and only if they are not adjacent in G. 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. It is not, however, the set complement of the graph; only the edges are complemented

What it means is that the complement of the graph will:

• have the same set of vertices.
• the edges which were not in the original graph will be in the complement graph
• and edges which were there in the original graph will not be there in the complement graph.

To get complement of a graph, add those edges that will make the graph complete, and remove the original edges.

In case of a complete graph, it's complement will be a null graph(i.e. same no. of vertices but no edges).

Another way to interpret is in matrix form.

For a graph, draw it's adjacency matrix, (i.e. M[i][j] = 1 if i and j are adjacent, otherwise M[i][j] = 0). To get the complement, change all 0's to 1's and 1's to 0's.

In case of a complete graph, all the entries will be 1. Hence, in complement graph's matrix all the entries will be 0, representing null graph.

Hope it helps :)

Comments

what does it means

The complement of a cycle on 25 vertices.

---

A cycle graph is such that every vertex is connected to it's two neighbouring vertices, such that the whole graph forms a cycle.For example n = 5:

So the complement of a cycle graph will be a graph such that each vertex is connected to all other vertices except two of them. For n = 25, it will be pretty big. But I think you can imagine it.