如果两个图包含相同数量的图顶点，且以相同方式连接，则称它们是同构的。形式上，如果存在 置换 
of 
使得 
在 图边 的集合 
中 当且仅当 
在 图边 的集合 
中，则具有 图顶点 
的两个图 
和 
被称为是同构的。
规范标记是用于确定图同构的一种实用有效技术。有几种软件实现可用，包括 nauty (McKay)、Traces (Piperno 2011; McKay and Piperno 2013)、saucy 和 bliss，其中后两者特别针对大型稀疏图。
可以使用 Wolfram 语言中的以下命令来确定两个图的等价性或不等价性IsomorphicGraphQ[g1, g2].
确定两个图是否同构被认为既不是 NP 完全问题 也不是 P 问题，尽管这尚未得到证明 (Skiena 1990, p. 181)。事实上，有一个著名的复杂度类叫做图同构完备，它被认为与 NP 完全 和 P 完全不相交。
然而，对于平面图（Hopcroft 和 Tarjan 1973，Hopcroft 和 Wong 1974）以及当最大顶点度受常数限制时（Luks 1982；Skiena 1990，p. 181），已知存在多项式时间算法。
在某种意义上，图同构在实践中很容易，除了一组病态的困难图似乎引起所有问题之外。因此，与结理论不同，从未出现过任何同构性未解决的重要图对。事实上，多年来，化学家一直在寻找一种易于计算的不变量，它可以区分代表分子的图。有整系列的论文，其中一位作者提出了一些不变量，另一位作者提供了一对该不变量无法区分的图，等等。不幸的是，几乎肯定没有简单的可计算的通用图不变量，无论是基于图谱还是图的任何其他参数（Royle 2004）。
算法。" J. Comput. Sys. Sci. 7, 323-331, 1973.Hopcroft, J. E. and Wong, J. K. "平面图同构的线性时间算法（初步报告）。" In STOC '74: Proceedings of the Sixth Annual ACM Symposium on Theory of Computing. New York: ACM, pp. 172-184, 1974.Junttila, T. A. and Kaski, P. "bliss."