In order to be able to apply graph canonical labelling and isomorphism checking within interactive theorem provers, either these checking algorithms must be mechanically verified, or their results must be verifiable by independent checkers. We analyze a state-of-the-art graph canonical labelling algorithm (described by McKay and Piperno) and formulate it in a form of a formal proof system. We provide an implementation that can export a proof that the obtained graph is the canonical form of a given graph. Such proofs are then verified by our independent checker, and can be used to certify that two given graphs are non-isomorphic.

翻译：为了能够在互动的理论验证中应用图形式金字塔标签和无形态式检查,这些核对算法必须机械地核实,或者其结果必须由独立的检查员核查。我们分析最先进的图形式卡通标签算法(由麦凯和皮佩诺描述),并以正式的验证系统的形式加以编制。我们提供了一个执行程序,可以输出一个证据,证明所获得的图表是某一图的典型形式。这些证据随后由我们的独立检查员核实,并可用于证明给定的两张图表是非单向式的。