Operations Of Graphs

Composition: The composition G = G1[G2] also has V = V1 × V2 as its point set, and u = (u1, u2) is adjacent with v = (v1, v2) whenever (u1 adj. v1) or (u1 = v1 and u2 adj. v1) For the graphs G1 and G2 of Figure. (a), both compositions G1[G2] and G2[G1] are shown in Figure (b).

Complement: The complement G′ of G is defined as a simple graph with the same vertex set as G and where two vertices u and v adjacent only when they are not adjacent in G.
For example,

A graph G is self-complementary if it is isomorphic to its complement. For example, the graphs

Self-complementary. The other self-complementary graph with five vertices is

Fusion: A pair of vertices v1 and v2 in graph G is said to be ‘fused’ if these two vertices are replaced by a single new vertex v such that every edge that was adjacent to either v1 or v2 or both is adjacent v. Thus we observe that the fusion of two vertices does not alter the number of edges of graph but reduced the vertices by one.

Theorem 1. For any graph G with six points, G or G contains a triangle.
Proof. Let v be a point of a graph G with six points. Since v is adjacent either in G or in G to the other five points of G. We can assume without loss of generality that there are three points u1, u2, u3 adjacent to v in G. If any two of these points are adjacent, then they are two points of a triangle whose third point is v. If no two of them are adjacent in G, then u1, u2 and u3 are the points of a triangle in G .