On the continuity of graph parameters

In this paper, we explore the mathematical properties of the distance function between graphs introduced by Bunke and Shearer. This distance metric is based on the maximum size of a common subgraph between two graphs. The notion of computing distance between graphs has proven useful in many areas involving graph based structures such as chemistry, biology and pattern recognition. The distance function studied here forms a metric on the set of isomorphism classes of graphs. We show that this metric induces the discrete topology. We also show that the distance between two graphs in the Erdös–Renyi probability space G(n,p)G(n,p) almost always is near the maximum attainable value. Finally, we define a notion of continuity of graph parameters and relate it to a property of graphs that can be easily verified.