Lesson plan
Graph isomorphism
In graph theory, an isomorphism of graphs G and H is a bijection between the vertex sets of G and H : f \colon V(G) \to V(H) such that any two vertices u and v of G are adjacent in G if and only if f(u) and f(v) 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, often denoted by G\simeq H . 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 automorphism of G. Graph isomorphism is an equivalence relation on graphs and as such it partitions the class of all graphs into equivalence classes. 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. The two graphs shown below are isomorphic, despite their different looking drawings.
Article summary
In graph theory, an isomorphism of graphs G and H is a bijection between the vertex sets of G and H : f \colon V(G) \to V(H) such that any two vertices u and v of G are adjacent in G if and only if f(u) and f(v) 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, often denoted by G\simeq H . 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 automorphism of G. Graph isomorphism is an equivalence relation on graphs and as such it partitions the class of all graphs into equivalence classes. 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. The two graphs shown below are isomorphic, despite their different looking drawings.
Key claims
- publication date: 2016 — source: Wikipedia, revision 1374954227, retrieved 2026-10-20 · confidence 0.95
Discussion questions
- Summarise the article in your own words. Which single claim would you verify first, and why?
- The record states that the publication date is "2016". What evidence would count against this claim?
- Which claim in this article is most likely to be revised as the sources update? How would you check its current status?
- If two sources disagreed about one of these facts, what would you need in order to trust one over the other?
Bibliography
- Wikipedia, “Graph isomorphism”, revision 1374954227, retrieved 2026-10-20 https://en.wikipedia.org/w/index.php?oldid=1374954227
Key claims and bibliography are generated from the same tracked claims and sources as the article page.