  This paper formulates a necessary and sufficient condition for a generic
graph matching problem to be equivalent to the maximum vertex and edge weight
clique problem in a derived association graph. The consequences of this results
are threefold: first, the condition is general enough to cover a broad range of
practical graph matching problems; second, a proof to establish equivalence
between graph matching and clique search reduces to showing that a given graph
matching problem satisfies the proposed condition; and third, the result sets
the scene for generic continuous solutions for a broad range of graph matching
problems. To illustrate the mathematical framework, we apply it to a number of
graph matching problems, including the problem of determining the graph edit
distance.
