§3. The index of intersection

L et us consider 2 examples of graphs, which could not be embedded in the plane.

Example 8. The graph “houses and wells”. Six point H₁, H₂, H₃ (the houses), W₁, W₂, W₃ (the wells) are given on the plain. The task is to draw the paths from each house to each well, so that these paths shouldn’t intersect. Is it possible to do? The answer is negative. If we draw all the paths except the last, there would be no place for the last one (pic. 12). We denote this graph as HW.

E xample 9. Consider the full graph with 5 vertexes, were each vertex is connected with 4 other ones. We denote it as FG₅.

I t is interesting to note, that these two graphs are the standards of graphs, that couldn’t be embedded in the plane. It means the following. If the graph couldn’t be embedded in the plane, then it contains one of the graphs HW or F5.

Exercises 15. Prove, that the following graph couldn’t be embedded in the plane.

16. Vertexes of a graph are the vertexes of the regular polygon with n angles and the edges are the sides and the shortest diagonals of the polygon. Prove, that for even n this graph could be embedded in the plane, and for odd n couldn’t be embedded.

17. Vertexes of a graph are the vertexes of the regular polygon with 2n angles and the edges are the sides and the longest diagonals of the polygon. Prove, that for n3 this graph couldn’t be embedded in the plane.

We will submit below the full prove, that the graphs HW or FG₅ couldn’t be embedded in the plane.

Definition. Let a and b are two segments on the plain and the end points of one segment does not belong to the other segment. We will write J(a, b)=1, if the segments intersects and J(a, b)=0, if the segments are not intersect. The value J(a, b) is called the intersection index for the segments a and b.

Definition. A finite set of segments on the plain is called a chain or a simple chain. The segments containing the chain are called its links and the end points of the links are called the vertexes. If the even number of links meets at each vertex, we call the chain to be a cycle.

Let x, y be two chains and the vertexes of one chain does not belong to the other chain. Let the chain x consists of segments a₁, a₂, …, a_m and the y consists of segments b₁, b₂, …, b_n. The sum

(;\s\do10(i =1(;\s\do10(j =1 J(a_i, b_j)

means the sum of all indexes of intersection of each link in x with each link in y. If this sum is even, we write J(x, y)=0, and if this sum is odd, we write J(x, y)=1. The value J(x, y) is called the intersection index of two chains x and y. We will prove, that index of intersection of two cycles is equal to zero.

Exercise 18. Prove, that any cycle is the join of several contours, which have no common links.

According to this result, it is sufficient to prove, the following theorem.

Theorem 4. Intersection index of two contours x and y is equal to zero.

Proof. First we move these contours a bit in order to make each link of x nonparallel to each link of y. This movement shouldn’t change the intersection index. Then we choose an arbitrary straight line l, which is not parallel to any straight line joining a vertex of x with a vertex of y. We begin to move the contour x continuously in the direction parallel to l. While the movement vertexes of x couldn’t meet the vertexes of y. So the intersection index could change only in the moment, when a vertex of one contour meet the link of the other contour. But in this moment the number of intersections can increases on 2, decreases on 2 (pic.15), or it can remain the same (pic.16). So, the number of intersections preserves its parity.

W e can move the contour x in the position, where it has no intersections with y. So J(x, y)=0 in this position and in any other position.

N ow we can prove, that HW-graph couldn’t be embedded in the plain. Two paths, that leads from different houses to different wells we will call nonadjacent. Lets draw all the paths (possibly with intersection) and denote I – the number of intersections of all the pairs of nonadjacent paths. We will prove that for any way of drawing the paths this number is odd.

Suppose, that we change the position of one path, for example H₁W₁. Let x be its old position, x be a new one. Nonadjacent to x are the following paths: H₂W₂, H₂W₃, H₃W₂ and H₃W₃. They form a cycle y=H₂W₂H₃W₃H₂. Two paths x and x also form a cycle. The index of intersection of these two cycles is equal to zero. It means, that the number of intersections of x and y has the same parity: J(x, y)=J(x, y).

Therefore it is obvious, that for any position of the paths on the plain the number I has the same parity. Really, we can change a position of the first path, then we change a position of the second path and so on. Finally we can obtain any prescribed position of the paths. We have the only one intersection on the picture 12. So, for any position of the paths on the plane the number I is odd and it is not equal to zero. Therefore the graph HW

Exercises 19. Prove, that the graph F5 couldn’t be embedded in the plane.

20. Prove, that on the sphere the index of intersection of any two cycles is equal to zero. Show, that there are two cycles on the torus, which has the only one intersection.

We considered above the segments without a direction. Let now a and b be the directed segments.

Definition. We move along the segment a and pay attention on the direction of b. If we note, that b intersects a from right to left we write J(a, b)=1. If we note that b intersects a from left to right we write J(a, b)=1. If a and b have no intersection, we write J(a, b)=0. The number J(a, b) we call an index of intersection of the directed segments a and b.

Definition. A finite set of directed segments on the plain we call an integer chain or simply a chain. Let the chain x consists of segments a₁, a₂, …, a_m and the y consists of segments b₁, b₂, …, b_n. An index of intersection of two integer chains x and y is defined as the sum

(;\s\do10(i =1(;\s\do10(j =1 J(a_i, b_j),

We say, that an integer chain is a cycle if for any vertex of the chain the number of links coming into the vertex and to a number of links coming out the vertex are equal.

Exercises 21. Consider a closed broken line and let us choose a direction on of going around this line. We call this line a directed contour. Prove that any integer cycle is a union of finite number of directed contours, which has no common links.

22. Prove, that the index of intersection of integer cycles is equal to zero.

2

pic.18

3. Consider a cycle, which consists of two directed contours a₁ and a₂ (pic.18). Let the point O be in the internal part of the ring and A be an arbitrary point. Let y be a directed broken line, that joins O and A. Prove, that A belongs to the external domain of the ring if and only if J(x, y)=2. In what case A belongs to the colored part of the ring?