On alternating products of graph relations

R. Bodendiek Institut f. Mathematik und ihre Didaktik Christian-Albrechts-Universität Kiel

R.Lang Fachbereich Informatik Universität Hamburg

Abstract

It is well-known that one can give an elegant version of the Kuratowskitype theorem for the projective plane by means of the five elementary relations R_{i}, i = 0, 1, …, 4, on the set Γ of all finite, undirected graphs without loops and multiple edges. Furthermore, these five relations play an interesting role in didactics of mathematics. Following a theory given in [2], C.Thies investigates them in [3]. In order to show that R_{0}, R_{1}, …, R_{4} are an appropriate curriculum he has to deal with so-called alternating products

RT (R_{i}) ∘ RT (R_{i}^{−1}) ∘ RT (R_{i}) ∘ RT (R_{i}^{−1}) ∘ …

or

RT (R_{i}^{−1}) ∘ RT (R_{i}) ∘ RT (R_{i}^{−1}) ∘ RT (R_{i}) ∘ …,

i = 0, 1, …, 4, where RT (R_{i}) denotes the reflexive transitive closure of R_{i} and RT (R_{i}^{−1}) = RT (R_{i})^{−1} the reflexive, transitive closure of R_{i}^{−1}. Here, it is shown that, in case of i = 0, there exists exactly one alternating product in the set of all alternating products of R_{0}, in case of i = 3 and i = 4 the sets of all alternating products of R_{3} and R_{4} are infinite sets.

1 Introduction

In the theory of embedding graphs into orientable and nonorientable surfaces, the five elementary relations R_{0}, R_{1}, …, R_{4}, introduced in [1], play an important role because it is possible to give elegant and precise definitions of the subgraph relation and the subdivision relation and the minor relation on the set Γ of all finite, undirected graphs without loops and multiple edges. Observing that an ordered pair (G, H) ∈ Γ × Γ belongs to R_{0} iff H arises from G by removing an edge e ∈ E(G) or an isolated vertex v ∈ V (G) the subgraph relation is equal to the reflexive, transitive closure RT (R_{0}) of R_{0}.

An ordered pair (G, H) ∈ Γ×Γ belongs to R_{1} iff H arises from G by contracting an edge e = {v, v′} ∈ E(G), provided at least one of the two endpoints v, v′ has got degree 1 or 2, and v, v′ do not have a common neighbour in G. If U_{1} = R_{0}∪R_{1}, then the well-known subdivision relation is equal to the reflexive, transitive closure RT (U_{1}) of U_{1} = R_{0} ∪ R_{1}.

To give a precise definition of the famous minor relation on Γ we need R_{0}, R_{1} and R_{2}. An ordered pair (G, H) ∈ Γ × Γ belongs to R_{2} iff H arises from G by the contraction of an edge e = {v, v′} ∈ E(G) provided v, v′ do not have a common neighbour in G, and both v and v′ have got a degree ≥ 3.

Figure 1:

If U_{2} denotes the union U_{2} = R_{0} ∪ R_{1} ∪ R_{2}, then the minor relation on Γ is equal to the reflexive, transitive closure RT (U_{2}) of U_{2} = R_{0} ∪ R_{1} ∪ R_{2}.

On alternating products of graph relations 3 Figure 2: Figure 3:

It is almost superflous to mention that RT (R_{0}), RT (U_{1}), RT (U_{2}) are partial ordering relations on Γ while R_{0}, R_{1}, R_{2} are not partial ordering relations on Γ.

Now, it remains to give the definition of R_{3} and R_{4}. The great advantage of R_{3} and R_{4} and their reflexive, transitive closures RT (U_{3}), RT (U_{4}), U_{i} = R_{0} ∪ R_{1} ∪ … ∪ R_{i}, i = 3, 4, is that we need essentially less graphs in order to characterize the set of all graphs not embeddable into an orientable or nonorientable surface.

Due to [1], an ordered pair (G, H) ∈ Γ×Γ belongs to R_{3} iff H arises from G by substituting a star S_{3} = {v} ∗ {v_{1}, v_{2}, v_{3}}, v, v_{1}, v_{2}, v_{3} ∈ V (G), by the triangle K_{3} = (v_{1}, v_{2}, v_{3}) provided {v_{1}, v_{2}, v_{3}} is an independent set in V.

Figure 1 shows that the octahedron O arises from the cube Q_{3} by applying R_{3} twice. In other words, we can say that the ordered pair (Q_{3}, O) ∈ R_{3} ∘ R_{3}, or equivalently (Q_{3}, O) ∈ RT (R_{3}).

Figure 2 shows a representation of the Petersen graph P and four other graphs R_{3}(P), R_{3}^{2}(P), R_{3}^{3}(P), R_{3}^{4}(P) in the projective plane such that it is clear that the ordered pair (P, K_{6}) ∈ R_{3} ∘R_{3} ∘R_{3} ∘R_{3}, or equivalently (P, K_{6}) ∈ RT (R_{3}).

Figure 4:

Due to [1] an ordered pair (G, H) ∈ Γ×Γ belongs to R_{4} iff H arises from G by substituting a double star D ⊆ G by a double triangle T (Figure 3) provided the edges {v_{1}, v_{2}} and {u_{1}, u_{2}} do not belong to G.

Figure 4 shows the decisive advantage of R_{4} because the two Kuratowski graphs K_{5} and K_{3,3} have got the property that the ordered pair (K_{3,3}, K_{5}) ∈ R_{4}.

2 Alternating products

In order to be able to define the concept of an alternating product it makes sense to introduce the converse relations of R_{i}, i = 0, 1, 2, 3, 4. Since we are going to restrict ourselves to the converse relations R_{0}^{−1}, R_{3}^{−1} and R_{4}^{−1} we omit the definitions of R_{1}^{−1} and R_{2}^{−1}.

Observing the definitions of R_{0}, R_{3} and R_{4} we obtain

a) an ordered pair (G, H) ∈ Γ×Γ belongs to R_{0}^{−1} iff H arises from G by adding an edge e ∈ 𝔓_{2}(V) − E or a new isolated vertex v ∉ V,

b) an ordered pair (G, H) ∈ Γ × Γ belongs to R_{3}^{−1} iff H arises from G by substituting a triangle C_{3} = (v_{1}, v_{2}, v_{3}) by the star v ∗ {v_{1}, v_{2}, v_{3}} such that v is a new vertex , not belonging to G,

c) an ordered pair (G, H) ∈ Γ × Γ belongs to R_{4}^{−1} iff H arises from G by substituting a double triangle T (1-amalgamation of two disjoint triangles) by a double trihedral D (double star) (Figure 3).

Observing RT (R_{i}^{−1}) = RT (R_{i})^{−1}, i = 0, 3, 4, we are able to introduce alternating products 𝔄_{i}(n) and 𝔅_{i}(n), i = 0, 3, 4, of n ∈ ℕ, n ≥ 2, factors as follows

𝔄_{i}(n) = \{ \begin{matrix}RT (R_{i}) ∘ RT (R_{i})^{−1} ∘ … ∘ RT (R_{i}) ∘ RT (R_{i})^{−1} & if n ≡ 0 mod 2, \\ RT (R_{i}) ∘ RT (R_{i})^{−1} ∘ … ∘ RT (R_{i})^{−1} ∘ RT (R_{i}) & if n ≡ 1 mod 2, \end{matrix}

𝔅_{i}(n) = \{ \begin{matrix}RT (R_{i})^{−1} ∘ RT (R_{i}) ∘ … ∘ RT (R_{i})^{−1} ∘ RT (R_{i}) & if n ≡ 0 mod 2, \\ RT (R_{i})^{−1} ∘ RT (R_{i}) ∘ … ∘ RT (R_{i}) ∘ RT (R_{i})^{−1} & if n ≡ 1 mod 2. \end{matrix}

If we denote the sets of all alternating products of R_{i}, i = 0, 3, 4, by A_{i} and B_{i}, defined as follows

A_{i} = {𝔄_{i}(n)|n ∈ ℕ − {1}}, B_{i} = {𝔅_{i}(n)|n ∈ ℕ − {1}},  (1)

we are going to investigate the question whether the sets A_{i} and B_{i}, i = 0, 3, 4, are finite or infinite.

3 The finiteness of A_{0} and B_{0}

Since first investigations lead to suppose that

A_{0} = {𝔄_{0}(2), 𝔄_{0}(3), 𝔄_{0}(4), …}  (2)

and

B_{0} = {𝔅_{0}(2), 𝔅_{0}(3), 𝔅_{0}(4), …}  (3)

are finite we first restrict ourselves to 𝔄_{0}(2) and 𝔅_{0}(2), and prove

Theorem 1

𝔄_{0}(2) = 𝔅_{0}(2) = Γ × Γ ⟺  (4)
RT (R_{0}) ∘ RT (R_{0})^{−1} = RT (R_{0})^{−1} ∘ RT (R_{0}) = Γ × Γ.

Proof: Because of RT (R_{0})∘RT (R_{0})^{−1} ⊆ Γ×Γ and RT (R_{0})^{−1}∘RT (R_{0}) ⊆ Γ×Γ it suffices to show the two inclusions (a) and (b) by

(a) RT (R_{0}) ∘ RT (R_{0})^{−1} ⊇ Γ × Γ and

(b) RT (R_{0})^{−1} ∘ RT (R_{0}) ⊇ Γ × Γ.

Ad (a) : Observing the definitions of a subset and a composition of relations the inclusion (a) is equivalent to the proposition

⋀_{(G,H)∈Γ×Γ} ⋁_{X∈Γ}[(G, X) ∈ RT (R_{0}) ∧ (X, H) ∈ RT (R_{0})^{−1}].  (5)

Assume (G, H) is any ordered pair in Γ×Γ. As the intersection graph G∩H is a subgraph of both G and H we obtain (G, G∩H) ∈ RT (R_{0}) and (H, G∩H) ∈ RT (R_{0}) such that (G ∩ H, H) ∈ RT (R_{0})^{−1}. Putting X = G ∩ H we obtain (G, G ∩ H) ∈ RT (R_{0}) and (G ∩ H, H) ∈ RT (R_{0})^{−1} such that (5) is true. This fact proves the inclusion (a).

Ad (b): Similarly to (a) the inclusion (b) is equivalent to the proposition (6) by

⋀_{(G,H)∈Γ×Γ} ⋁_{Y ∈Γ}[(G, Y) ∈ RT (R_{0})^{−1} ∧ (Y, H) ∈ RT (R_{0})].  (6)

The proof of (6) is done by choosing Y = G ∪ H(= union graph of G and H) for any graphs G, H ∈ Γ for G and H are subgraphs of Y = G ∪ H implying (G ∪ H, G) ∈ RT (R_{0}), (G ∪ H, H) ∈ RT (R_{0}) and (G, G ∪ H) ∈ RT (R_{0})^{−1}. This proves (b).

The answer of the question asked above concerning the finiteness of A_{0} and B_{0} is an immediate consequence of theorem 1 and says as follows

Theorem 2 A_{0} and B_{0} are equal, finite sets and consist of exactly one element x = Γ × Γ, i.e. A_{0} = B_{0} = {Γ × Γ}.

Proof: Observing Theorem l and the fact that the composition of relations on the sets of all relations on Γ is an associative binary operation, the statement of Theorem 2 has been proved iff the two inclusions (7) and (8) by

Γ × Γ ⊆ (Γ × Γ) ∘ RT (R_{0})  (7)

and

Γ × Γ ⊆ (Γ × Γ) ∘ RT (R_{0})^{−1}  (8)

are true. It is obvious that (7) is true iff the statement

⋀_{(G,H)∈Γ×Γ} ⋁_{X∈Γ}[(G, X) ∈ Γ × Γ ∧ (X, H) ∈ RT (R_{0})]  (9)

holds. Choosing X = H for any (G, H) ∈ Γ × Γ we recognize immediately that (7) is true.

The proof of (8) is quite the same as the one of (7) such that we are allowed to omit details. This proves Theorem 2.

After this beautiful proof we are going to turn to A_{3} and B_{3} and want to investigate the question whether these two sets are also finite.

4 The infinity of A_{3} and B_{3}

Figure 5 shows the five graphs G, G_{1}, G_{2}, G_{3} and H that can be characterized by means of R_{3} and R_{3}^{−1} represented in Figure 6. It shows that the ordered pair (G, H) belongs to 𝔄_{3}(4) = RT (R_{3}) ∘ RT (R_{3})^{−1} ∘ RT (R_{3}) ∘ RT (R_{3})^{−1}

Figure 5:

but it is neither an element of 𝔄_{3}(3) nor of 𝔄_{3}(2). This fact implies that 𝔄_{3}(4) ≠ 𝔄_{3}(i), i = 2, 3.

Therefore, it is obvious that A_{3} has at least the three elements 𝔄_{3}(2), 𝔄_{3}(3) and 𝔄_{3}(4).

This fact implies that the situation of A_{3} and B_{3} is quite different from the situation of A_{0} and B_{0} such that we suppose that are A_{3} and B_{3} are even infinite sets. In order to give a proof of this assumption we generalize the example of figure 5 and prove

Theorem 3 A_{3} and B_{3} are infinite sets.

Proof: (1) In order to show that A_{3} is infinite we suppose to argue by con-

Figure 6:

tradiction that A_{3} is finite. Then there necessarily exists a natural number n ∈ ℕ, n ≥ 3, such that A_{3} = {𝔄_{3}(2), 𝔄_{3}(4), …, 𝔄_{3}(n − 1)} with the property that there is an element k ∈ {2, 3, …, n − 1} for which the equality 𝔄_{3}(k) = 𝔄_{3}(n) holds. This is a contradiction to statement (10) by

⋀_{i∈{2,3,...,n−1}} 𝔄_{3}(n) ⊈ 𝔄_{3}(i).  (10)

In order to show that (10) is true we argue as follows. (10) is obviously shown, if and only if, we give an ordered pair (G, H) ∈ 𝔄_{3}(n) not belonging to 𝔄_{3}(i) for any i ∈ {2, 3, …, n − 1}. It turns out that it is even possible to show that there is an ordered pair (G, H) ∈ 𝔄_{3}(n) not belonging to 𝔄_{3}(i) for every i ∈ {2, 3, …, n − 1}. If n = 2k, k ≥ 1, is even then we generalize the graph G from Figure 5. Thus we consider the graphs G = G(k) and H = G_{n} depicted in Figure 7. Generalizing the diagram of Figure 6 we recognize that the ordered pair (G, H) = (G(k), G_{n}) is an element of

𝔄_{3}(n) = RT (R_{3}) ∘ RT (R_{3})^{−1} ∘ … ∘ RT (R_{3}) ∘ RT (R_{3})^{−1}  (11)

but

(G, H) = (G(k), G_{n}) ∉ 𝔄_{3}(i)

10 R. Bodendiek and R. Lang Figure 7: for each i = 2, 3, …, n − 1.

Since the proof of these two statements is a matter of routine checking, we are allowed to omit details. In the case of odd n = 2k + 1, k ≥ 1, we can argue by observing Figure 8 and choosing (G, H) = (G′(k), Gn^{′}). A routine checking shows that (G, H) ∈ 𝔄_{3}(n), but (G, H) ∉ 𝔄_{3}(i) for each i = 2, 3, …, n − 1. After all, (10) is proved. This implies that our assumption is false and A_{3} is infinite.

(2) To argue by contradiction we assume that B_{3} is finite. Then there exists an integer n ≥ 3 such that B_{3} = {𝔅_{3}(2), 𝔅_{3}(3), …, 𝔅_{3}(n − 1)} with the property that there is an element k ∈ {2, 3, …, n − 1} for which 𝔄_{3}(n) is equal to 𝔄_{3}(k). This equality is a contradiction to statement (12) by

⋀_{i∈{2,3,...,n−1}} 𝔅_{3}(n) ⊈ 𝔅_{3}(i).  (12)

We prove (12) by showing the existence of an ordered pair (G, H) ∈ 𝔅_{3}(n) not belonging to 𝔅_{3}(i) for every i ∈ {2, 3, …, n − 1}.

It is useful to distinguish the two cases

(a) n ≡ 0 mod 2 and

(b) n ≡ 1 mod 2.

In (a) we take G = X(k), n = 2k + 2, k ≥ 1, k = \frac{n−2}{2} and H = X_{2k} represented in Figure 9. Observing Figure 9 the proof of (G, H) ∈ 𝔅_{3}(n) and (G, H) ∉ 𝔅_{3}(i) for each i = 2, 3, …, n − 1 is a matter of routine checking.

In case (b), n is odd such that n = 2k + 1, k ≥ 1. Then we choose for G, H the graphs Y (k) and Y_{2k+1} depicted in Figure 10. It is easy to see that (G, H) ∈ 𝔅_{3}(n) and (G, H) ∉ 𝔅_{3}(i) for each i = 2, 3, …, n − 1. Hence, the assumption is not true. That means that B_{3} is infinite.

5 The infinity of A_{4} and B_{4}

In this section we turn toward the elementary relation R_{1}. After having seen that A_{3} and B_{3} are infinite sets it is not difficult to guess that A_{4} and B_{4} are also infinite sets. The confirmation of this guess is given in

Theorem 4 A_{4} and B_{4} are infinite sets.

12 R. Bodendiek and R. Lang Figure 8:

On alternating products of graph relations 13 Figure 9:

14 R. Bodendiek and R. Lang Figure 10:

Proof: (1) It is evident that the main idea of this proof is similar to the idea of the proof of (1) in Theorem 3. Therefore, we omit details and restrict ourselves to the proof of statement (13) by

⋀_{i∈{2,3,...,n−1}} 𝔄_{4}(n) ⊈ 𝔄_{4}(i),  (13)

where n is assumed to be a positive integer ≥ 3 with the property that A_{4} consists of the elements 𝔄_{4}(2), 𝔄_{4}(3), …, 𝔄_{4}(n−1). In order to find an ordered pair (G, H) ∈ 𝔄_{4}(n) not belonging to each 𝔄_{4}(i), i = 2, 3, …, n − 1, we distinguish the two cases n ≡ 0 mod 2 and n ≡ 1 mod 2. In the first case n ≡ 0 mod 2, Figure 11 shows the graphs G = G(n) and H = G_{n} satisfying the properties mentioned above. The proof is not quite easy. In spite of his fact we cannot deal with details. In the second case n ≡ 1 mod 2, Figure 12 depicts the corresponding graphs G = H(n) and H = H_{n}. It is clear by means of Figure 12 that (G, H) ∈ 𝔄_{4}(n) and (G, H) ∉ 𝔄_{4}(i) for each i = 2, 3, …, n−1 are true. This completes the proof of (1).

Now we conclude by giving a sketch of the proof of (2), where (2) says that 𝔅_{4} is infinite. Having assumed that B_{4} is finite we have to prove the statement

⋀_{i∈{2,3,...,n−1}} 𝔅_{4}(n) ⊈ 𝔅_{4}(i).  (14)

by giving an ordered pair (G, H) ∈ 𝔅_{4}(n) not belonging to each 𝔅_{4}(i), i = 2, 3, …, n − 1, where n is chosen as explained above. If n ≡ 0 mod 2 Figure 13 proves that (14) is true for even n and G = X(n) and H = X_{n}.

If n ≡ 1 mod 2 we choose G = Y (n) and H = Y_{n}. Figure 14 shows that (G, H) ∈ 𝔅_{4}(n) and (G, H) ∉ 𝔅_{4}(i) for each i = 2, 3, …, n−1. This completes the proof in the case (2). That means that B_{4} is infinite.

16 R. Bodendiek and R. Lang Figure 11:

On alternating products of graph relations 17 Figure 12:

18 R. Bodendiek and R. Lang Figure 13:

On alternating products of graph relations 19 Figure 14:

References

[1] R.Bodendiek, H.Schumacher, K.Wagner. Über Relationen auf Graphenmengen. Abhandlungen aus dem mathematischen Seminar der Universität Hamburg 51, 1981.

[2] D.Sawada. An assessment of a selected set of Piagetian-derived operators for the generation of effective learning hierarachies. JRME 1973.

[3] C.Thies. Zur Formalisierung des Piagetschen Gruppierungsbegriffs unter besonderer Berücksichtigung graphentheoreticher Relationen. Dissertation Kiel, 1983.

[4] K.Wagner, R.Bodendiek. Graphentheorie I, BI-Wissenschaftsverlag Mannheim 1989.

[5] K.Wagner, R.Bodendiek. Graphentheorie II, BI-Wissenschaftsverlag Mannheim 1990.

[6] K.Wagner, R.Bodendiek. Graphentheorie III, BI-Wissenschaftsverlag Mannheim 1992.