Graphs 001

Definitions and examples

A (finite, simple) graph G is an ordered pair G=(V(G),E(G)) of two finite sets, where E(G) is a set of 2-element subsets of V(G). The vertices of G are the elements of V(G), and the edges of G are the elements of E(G). The order |G| of the graph G is the cardinality of V(G).

For example, we obtain a graph G=(V(G),E(G)) by: V(G)=\{1,2,3\}, E(G)=\bigl\{\{1,2\},\{2,3\}\bigr\}, which we can draw as follows:

path of length 2

If \{x,y\}\in E(G), we say that x, y are adjacent, or neighbors, and we denote it by x\sim y.

Two graphs G_1, G_2 are isomorphic if there is a bijection f\colon V(G_1)\to V(G_2) such that x\sim y if and only if f(x)\sim f(y). In this case, we write G_1\cong G_2. 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.

three graphs, aligned

Exercises

  1. Determine the two graphs that are isomorphic.
  2. Show that, in our setting of finite graphs, it is actually enough to check that f is a bijection of vertex sets such that x\sim y implies f(x)\sim f(y), in order to show that f is a graph isomorphism.
  3. Prove that:
    • for any graph G, G\cong G,
    • if f\colon G_1\to G_2 is an isomorphism, then f^{-1}\colon G_2\to G_1 is an isomorphism.
    • if f_1\colon G_1\to G_2, and f_2\colon G_2\to G_3 are isomorphisms, then f_2\circ f_1 is an isomorphism.

Advertisements
This entry was posted in Math and tagged . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s