Editing Graph isomorphism (section)

{{Short description|Bijection between the vertex set of two graphs}}
In [[graph theory]], an '''isomorphism of [[Graph (discrete mathematics)|graphs]]''' ''G'' and ''H'' is a [[bijection]] between the vertex sets of ''G'' and ''H''
:<math> f \colon V(G) \to V(H) </math>
such that any two vertices ''u'' and ''v'' of ''G'' are [[Adjacent (graph theory)|adjacent]] in ''G'' [[if and only if]] <math>f(u)</math> and <math>f(v)</math> are adjacent in ''H''. This kind of bijection is commonly described as "edge-preserving bijection", in accordance with the general notion of [[isomorphism]] being a structure-preserving bijection.

If an [[isomorphism]] exists between two graphs, then the graphs are called '''isomorphic''' and denoted as <math>G\simeq H</math>. In the case when the isomorphism is a mapping of a graph onto itself, i.e., when ''G'' and ''H'' are one and the same graph, the isomorphism is called an [[graph automorphism|automorphism]] of ''G''.

Graph isomorphism is an [[equivalence relation]] on graphs and as such it partitions the [[class (set theory)|class]] of all graphs into [[equivalence class]]es. A set of graphs isomorphic to each other is called an '''[[isomorphism class]]''' of graphs. The question of whether graph isomorphism can be determined in polynomial time is a major unsolved problem in computer science, known as the [[graph isomorphism problem]].<ref>{{Cite journal |last=Grohe |first=Martin |date=2020-11-01 |title=The Graph Isomorphism Problem |volume=63 |pages=128–134 |journal=[[Communications of the ACM]] |issue=11 |url=https://cacm.acm.org/magazines/2020/11/248220-the-graph-isomorphism-problem/abstract |access-date=2023-03-06 |doi=10.1145/3372123}}</ref><ref>{{Cite news |last=Klarreich |first=Erica |date=2015-12-14 |title=Landmark Algorithm Breaks 30-Year Impasse |work=[[Quanta Magazine]] |url=https://www.quantamagazine.org/algorithm-solves-graph-isomorphism-in-record-time-20151214/ |access-date=2023-03-06}}</ref>

The two graphs shown below are isomorphic, despite their different looking [[graph drawing|drawings]].

{|class="wikitable" style="margin: 1em auto 1em auto"
! Graph G
! Graph H
! An isomorphism<br />between G and H
|-
|style="padding-left:2em;padding-right:2em;"|[[File:Graph isomorphism a.svg|class=skin-invert|100px]]
|style="padding-left:1em;padding-right:1em;"|[[File:Graph isomorphism b.svg|class=skin-invert|210px]]
|align="center" |''f''(''a'') = 1

''f''(''b'') = 6

''f''(''c'') = 8

''f''(''d'') = 3

''f''(''g'') = 5

''f''(''h'') = 2

''f''(''i'') = 4

''f''(''j'') = 7
|}