1.1 Lecture 1. Drawing

We are starting with some elementary things, which infact do not require any special knowledge. Unknown words can be simply omitted without loss of the understanding of the main subject. However in Appendix we introduce briefly some basic concepts of general topology. If you feel, you need this, you may go to Section .

We assume all the topological spaces to be Hausdorff. All subsets of topological spaces are considered with the induced topology. In order to shorten the notations we further denote topological spaces by $X$ , without precisely pointing out the topology, if this does not lead to misunderstandings.

In some sense the graphs constitute the simplest nontrivial class of topological objects of finite type. Indeed, the zero-dimensional topological spaces of finite type would be just finite sets with the discrete topology. Graphs are one-dimensional according to several definitions from which we choose the simplest ones.

Informally, graphs are several points some of which are connected by arcs.

Example 1.1.1   Below it is a graph, but also it may be considered as several different graphs.

Exercise 1.1.2   Mark by points a dozen of people you know. Which of them know each other? Join all such pairs by arcs.

You have constructed a graph. Is it connected?

Add a point for yourself. Before you draw the arcs as above can you be sure that the resulting graph will be connected?

Suggest an informal definition of the connected graph.

Exercise 1.1.3   Mark by points a dozen of cities that come to your mind. You might suppose (or know for sure) that some of them are related by the direct airlines. Represent this structure by a graph; it would be a good idea to represent on your graph the information about several airlines that, perhaps, relate some of your cities.

Ignore the cities without airports as well as the ones not related with any of your cities (in the graph theory terminology they are isolated). Suppose your graph is connected; otherwise add some imaginary airlines in order to make it connected.

Find a pair of cities that are the most inconvenient to travel from one to another by air; that is, let such travels demand the maximal number of transfers. (It is unlikely that none of the considered travels demand transfers; in this case your graph is called complete).

Suggest an informal definition of the diameter of a graph.

In graph theory the points ("people" and "cities" in the above exercises) are called vertices and the arcs are called edges.

Now we can provide some formal definitions:

Definition 1.1.4   A graph is a pair of Hausdorff spaces $X_0\subset X_1$ such that

(i)

$X_0$ is a finite set;

(ii)

$X_1$ is a compact set;

(iii)

the difference $X_1\setminus X_0$ is homeomorphic to a finite disjoint union of open intervals (with the induced topology from Example (1)).

Definition 1.1.5   Elements of $X_0$ are called vertices of the graph.

Control question 1.1   What are edges of the graph?

We denote the set of all edges of a graph by $E$ .

Control question 1.2   Will the concept of graph remain the same if we omit the Hausdorff assumption in the above definition?

Control question 1.3   Will the concept of graph remain the same if we omit the assumption that $X_1$ is compact?

Please, use the answer form at the end of this lecture to answer this questions.

Definition 1.1.6   A vertex $v\in X_0$ is called isolated if there exists a neighborhood $U(v)\subseteq X_1$ such that $U(v)\cap X_1=\{v\}$ .

Definition 1.1.7   A graph $X_0\subset X_1$ is said to be connected if $X_1$ is a connected topological space.

Control question 1.4   Given natural numbers $\alpha$ and $n$ , suggest a necessary condition for the existence of a graph with $\alpha$ vertices and $n$ edges such that
a) it has no isolated points;
b) it is connected.

Are the proposed conditions sufficient for a graph to satisfy the aforesaid properties?

The answer form for this question is at the end of the lecture.

Definition 1.1.8   A vertex $v\in X_0$ and an edge $e\in E$ are said to be incident if for any neighborhood $U(v)\subseteq X_1$ it holds that $U(v)\cap e\ne\emptyset$ .

Definition 1.1.9   A sequence of vertices $v_1,\ldots,v_k\in X_0$ and edges $e_1,\ldots, e_{k-1}\in E$ is called a chain if $e_i$ is incident to $v_i$ and $v_{i+1}$ for all $i=1,\ldots,k-1$ , and $e_i\ne e_j$ for all $i\ne j$ . The chain is called closed if $v_1=v_k$ and unclosed otherwise. A length of the chain is $k-1$ . The vertices $v_1$ and $v_{k}$ are said to be end vertices of the chain.

Definition 1.1.10   Let the graph $X_0\subset X_1$ be connected. A distance between two given vertices $u,v\in X_0$ is the smallest length of any chain with the end vertices $u$ and $v$ . A maximal distance over all pairs of vertices in this graph is called a diameter of the graph.

Definition 1.1.11   The graphs $X_0\subset X_1$ and $Y_0\subset Y_1$ are called isomorphic if they are homeomorphic as pairs of topological spaces, i.e. if there exists such a homeomorphism $h:X_1\longrightarrow Y_1$ that $h(X_0)\subset Y_0$ and $h:X_0\longrightarrow Y_0$ is a bijection.

Exercise 1.1.12   Represent by graphs all the letters of the alphabet of your native language. Don't forget to put a vertice on o! Which of the resulting graphs are isomorphic? What are the diameters of the connected ones?

Control question 1.5  

Control question 1.6