Abstract
The execution time of an algorithm to produce all maximal compatibles [1] given all pair wise compatible states of a finite state machine is strongly dependent on the number of such maximal compatibles possible in an N state machine. The problem of finding the maximum number of such maximal compatibles is equivalent to the problem of finding the maximum possible number of completely connected sub graphs, not included in any other such sub graphs, in an N node graph. The relation of these two problems has been disscussed by R. Das [2]. In this paper the problem is considered in its graph formulation. It is shown that if a graph has the maximum number of such sub graphs they must each contain the same number of nodes and that the maximum number of such subgraphs for N node graphs is =3 if N is divisible by 3, (2/3)2 . 3[N/3] if N mod 3 = 1, and (2/3).3[N/3] if N mod 3 = 2. A bound on the number of such sub graphs is also given in terms of the degree of the nodes of the graph.