A Combinatorial Study of the Notion of Graph Space

Abstract

This paper proposes study of the connectivity criteria of undirected simple graphs. Given the number of vertices ‘V’, one should
be able to introduce connectivity between any two vertices by means of an edge. ‘Simple graph’ is the one where pairs of
vertices are connected just by one edge. If any pair of vertices has more than one edge, then it is called ‘multigraph’. In t his
research we are concerned with undirected simple graphs only. Multigraphs are just extensions of simple graphs. Given a finite
number of vertices, one can construct potentially infinite multigraphs, of which number of simple graphs would be finite.
Alternatively, if the number of vertices is increased, number of simple graphs constructed would also increase exponentially.
For example, for a single vertex, 2 graphs could be constructed. For two vertices, one can construct 4 graphs. For three vertices,
one can construct 50 graphs. For four vertices, one can construct 946 graphs. For five vertices, 31,714 graphs could be
constructed. One can construct 2,064,322 graphs from six vertices. As number of vertices tends to infinity, potentially infinite
simple graphs could be constructed which amounts to what we call as “Graph Space”. All kinds of graphs are sub spaces of
Graph Space, which is closed under all types of graph theoretic operations.