## 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.

## Exercises

- 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.

Advertisements