[PDF][PDF] Some remarks on the theory of graphs
P Erdös - 1947 - projecteuclid.org
1947•projecteuclid.org
The present note consists of some remarks on graphs. A graph G is a set of points some of
which are connected by edges. We assume here that no two points are connected by more
than one edge. The complementary graph G'of G has the same vertices as G and two points
are connected in G'if and only if they are not connected in G. A special case of a theorem of
Ramsey can be stated in graph theoretic language as follows: There exists a function f (k, I)
of positive integers k, I with the following property. Let there be given a graph G of n* zf (kf I) …
which are connected by edges. We assume here that no two points are connected by more
than one edge. The complementary graph G'of G has the same vertices as G and two points
are connected in G'if and only if they are not connected in G. A special case of a theorem of
Ramsey can be stated in graph theoretic language as follows: There exists a function f (k, I)
of positive integers k, I with the following property. Let there be given a graph G of n* zf (kf I) …
The present note consists of some remarks on graphs. A graph G is a set of points some of which are connected by edges. We assume here that no two points are connected by more than one edge. The complementary graph G'of G has the same vertices as G and two points are connected in G'if and only if they are not connected in G. A special case of a theorem of Ramsey can be stated in graph theoretic language as follows:
There exists a function f (k, I) of positive integers k, I with the following property. Let there be given a graph G of n* zf (kf I) vertices. Then either G contains a complete graph of order fe, or G'a complete graph of order L (A complete graph is a graph any two vertices of which are connected. The order of a complete graph is the number of its vertices.)
Project Euclid