Department of Mathematics Elementary Graph Theory Lecture 5
The complement G′ of G is defined as a simple graph with the same vertex set
as G and two vertices u and v are adjacent only when they are not adjacent in
G.
A graph G is called self-complementary graph if it is isomorphic to its
complement
Problem: If a simple graph with n-vertices is isomorphic with its complement, how
many vertices will that have ?
Solution: Let q be the number of edges of G and q be the number of edges in the
complement G , then
p( p 1)
q q
2
If G is a self-complementary graph, then q q
p( p 1) p( p 1)
2q q
2 4
Hence, in a self-complementary graph p or p 1 must be divisible by 4.
** from the above problem we get that, there exist no self-complementary graph of
order 2, 3, 6, 7, 10, 11, …
Dr. Didar A. Ali 1
, Department of Mathematics Elementary Graph Theory Lecture 5
Ramsey Theory
Theorem: For any graph G with six vertices, G or G contains a triangle.
(Given a group of six people we can always find either three who all know
each other or three who don’t know each other)
Proof: Let v be any vertex of a graph G with six vertices. Since v is adjacent either
in G or in G to the other five vertices of G.
Assume that, without loss of generality v is adjacent to three vertices u1, u2, u3 in G.
If any two of these vertices of u1, u2 and u3 are adjacent in G, then they are two
vertices of a triangle whose third vertex is v.
If no two of them are adjacent in G, then u1, u2 and u3 are the vertices of a
triangle in G .
Ramsey number
Ramsey number R(m, n) is the smallest integer number, such that every graph
of order R(m, n) contains a subgraph K m or K n .
Dr. Didar A. Ali 2
The complement G′ of G is defined as a simple graph with the same vertex set
as G and two vertices u and v are adjacent only when they are not adjacent in
G.
A graph G is called self-complementary graph if it is isomorphic to its
complement
Problem: If a simple graph with n-vertices is isomorphic with its complement, how
many vertices will that have ?
Solution: Let q be the number of edges of G and q be the number of edges in the
complement G , then
p( p 1)
q q
2
If G is a self-complementary graph, then q q
p( p 1) p( p 1)
2q q
2 4
Hence, in a self-complementary graph p or p 1 must be divisible by 4.
** from the above problem we get that, there exist no self-complementary graph of
order 2, 3, 6, 7, 10, 11, …
Dr. Didar A. Ali 1
, Department of Mathematics Elementary Graph Theory Lecture 5
Ramsey Theory
Theorem: For any graph G with six vertices, G or G contains a triangle.
(Given a group of six people we can always find either three who all know
each other or three who don’t know each other)
Proof: Let v be any vertex of a graph G with six vertices. Since v is adjacent either
in G or in G to the other five vertices of G.
Assume that, without loss of generality v is adjacent to three vertices u1, u2, u3 in G.
If any two of these vertices of u1, u2 and u3 are adjacent in G, then they are two
vertices of a triangle whose third vertex is v.
If no two of them are adjacent in G, then u1, u2 and u3 are the vertices of a
triangle in G .
Ramsey number
Ramsey number R(m, n) is the smallest integer number, such that every graph
of order R(m, n) contains a subgraph K m or K n .
Dr. Didar A. Ali 2
