Definitions and examples
A (finite, simple) graph is an ordered pair of two finite sets, where is a set of -element subsets of . The vertices of are the elements of , and the edges of are the elements of . The order of the graph is the cardinality of .
For example, we obtain a graph by: , , which we can draw as follows:
If , we say that , are adjacent, or neighbors, and we denote it by .
Two graphs , are isomorphic if there is a bijection such that if and only if . In this case, we write . We usually do not distinguish between isomorphic graphs.
It is not always easy to determine whether two graphs are isomorphic or not. For example, in the next three graphs, there are exactly two which are isomorphic.
- Determine the two graphs that are isomorphic.
- Show that, in our setting of finite graphs, it is actually enough to check that is a bijection of vertex sets such that implies , in order to show that is a graph isomorphism.
- Prove that:
- for any graph , ,
- if is an isomorphism, then is an isomorphism.
- if , and are isomorphisms, then is an isomorphism.