Evolutionary Families of Sets

C. H. C. Little and A. E. Campbell Massey University Palmerston North New Zealand

                           c.little@massey.ac.nz
                        allistercampbell@yahoo.com

Abstract

A finite family of subsets of a finite set is said to be evolutionary if its members can be ordered so that each subset except the first has an element in the union of the previous subsets and also an element not in that union. The study of evolutionary families is motivated by a conjecture of Naddef and Pulleyblank concerning ear decompositions of 1-extendable graphs. The present paper gives some sufficient conditions for a family to be evolutionary.

Received: November 25, 1998; Accepted: January 29, 2000. Mathematical Reviews Subject Numbers: 03E05, 05C70

1 Introduction

The motivation for the concept of an evolutionary family of sets lies in a conjecture of Naddef and Pulleyblank [5]. This conjecture has recently been proved by Carvalho, Lucchesi and Murty [2]. In order to explain this theorem, we need several definitions concerning 1-factors of graphs. We adopt the terminology and notation found in [1]. In this paper, graphs will be assumed to be finite and to have no loops or multiple edges. A 1-factor in such a graph G is a set F of edges such that |F ∩ ∂v| = 1 for each v ∈ V G. A graph is 1-extendable if for each edge e there is a 1-factor containing e. An alternating circuit is a circuit which is the sum (symmetric difference) of two 1-factors. A set S of alternating circuits is consanguineous (with respect) to a 1-factor F if each circuit in S has half its edges in F. Note that if G is a connected 1-extendable graph with more than one edge, then every edge of G belongs to an alternating circuit. The alternating circuits span a subspace of the cycle space of G. This space is called the alternating space, and is denoted by A(G).

Now let H be a subgraph of a graph G. An ear of G (with respect to H) is a path in G, of odd length, joining vertices of H but having no edges or internal vertices belonging to H. Let S be a set of n vertex-disjoint ears of G with respect to H. If each vertex and edge of G is in H or a member of S, then we say that G is obtained from H by an n-ear addition.

Let G be a 1-extendable graph. An ear decomposition of G of length n is a sequence (G_{0}, G_{1}, …, G_{n}) of graphs such that the following conditions hold:

1. G_{0} consists of an edge of G, together with its ends;

2. G_{n} = G;

3. for each i > 0 the graph G_{i} is 1-extendable and obtained from G_{i−1} by the addition of a set of vertex-disjoint ears.

It is well known that there is a unique 1-factor F of G such that F ∩ EG_{i} is a 1-factor of G_{i} for each i. We say that F is associated with the decomposition. For each i > 0 and each ear of G_{i} with respect to G_{i−1} there exists an alternating circuit of G_{i} that includes the ear and is consanguineous to F ∩ G_{i}.

The following theorem has been proved by Lovász and Plummer [4] [p. 182].

Theorem 1 A 1-extendable graph has an ear decomposition (G_{0}, G_{1}, …, G_{n}) in which, for each i > 0, the graph G_{i} is obtained from G_{i−1} by a 1- or 2-ear addition.

In view of Theorem 1, let us define an ear decomposition of a 1-extendable graph to be permissible if each graph in the decomposition (other than the first) is obtained from the preceding one by the addition of no more than two ears, and no 2-ear addition can be replaced by a pair of 1-ear additions. The latter clause shows that in the case of a 2-ear addition there is no alternating circuit which is consanguineous to the associated 1-factor and includes just one of the ears.

One question addressed by Naddef and Pulleyblank [5] concerns the smallest number of 2-ear additions in a permissible decomposition. It is easy to obtain a lower bound for this number. Indeed, if we denote by C(G) the cycle space of a graph G, then the number of ears added in the course of the decomposition is dim C(G), for if G is obtained from a subgraph H by an n-ear addition then

dim C(G) − dim C(H) = n.

On the other hand,

dim A(G) − dim A(H) ≥ 1.

These results imply that a lower bound for the number of 2-ear additions in a permissible ear decomposition is given by dim C(G) − dim A(G). The theorem of Carvalho, Lucchesi and Murty alluded to earlier is that this lower bound can always be met.

Theorem 2 [2] The minimum number of 2-ear additions in a permissible ear decomposition of a 1-extendable graph G is dim C(G) − dim A(G).

For convenience we shall call the number dim C(G) − dim A(G) the Naddef-Pulleyblank bound.

Let (G_{0}, G_{1}, …, G_{n}) be an ear decomposition of a 1-extendable graph G. If for each i > 0 we select an alternating circuit which is consanguineous to the associated 1-factor and includes the ear or ears of G_{i} with respect to G_{i−1}, then the resulting set of alternating circuits is linearly independent. In fact, if the decomposition is permissible and the number of 2-ear additions is dim C(G) − dim A(G), then these alternating circuits supply a basis for A(G). Thus dim A(G) = n. Let us denote this basis by (A_{1}, A_{2}, …, A_{n}), where for each i we have A_{i} ⊆ EG_{i}. Note that for each i > 0 we have the following properties:

1. A_{i} ∩ EG_{i−1} ≠ ∅;

2. A_{i} ∩ (EG − EG_{i−1}) ≠ ∅.

Roughly speaking, these conditions mean that A_{i} contains something old (in other words, in EG_{i−1}) and something new (in EG − EG_{i−1}). They motivate the following definition.

Definition 1 Let S be a finite family of subsets of a finite set S. We say that S is evolutionary if there exists an ordering (S_{1}, S_{2}, …, S_{n}) of the sets in S such that for each i > 1 we have

S_{i} ∩ ⋃_{j=1}^{i−1} S_{j} ≠ ∅  (1)

and

S_{i} ∩ (S − ⋃_{j=1}^{i−1} S_{j}) ≠ ∅.  (2)

The ordering (S_{1}, S_{2}, …, S_{n}) is also said to be evolutionary.

For example, the family {{1}, {1, 2}, {2, 3}} has evolutionary ordering

({1}, {1, 2}, {2, 3}),

but the family {{1}, {2}, {1, 2, 3}} is not evolutionary.

Thus if a 1-extendable graph G has a permissible ear decomposition with the number of 2-ear additions meeting the Naddef-Pulleyblank bound, then its alternating space has a consanguineous evolutionary basis. Conversely, suppose that A(G) has such a basis, with evolutionary ordering (A_{1}, A_{2}, …, A_{n}). We propose to construct a permissible ear decomposition of G with the number of 2-ear additions meeting the Naddef-Pulleyblank bound. First, define G_{0} = G[{e}] for any e ∈ A_{1}, and for each i > 0 define G_{i} = G[∪_{j=1}^{i}A_{j}]. Since the basis of A(G) is evolutionary, it follows that (G_{0}, G_{1}, …, G_{n}) is an ear decomposition of G. As dim A(G) = n, there is no longer ear decomposition of G. In fact, (G_{0}, G_{1}, …, G_{i}) is a longest ear decomposition of G_{i}, for each i > 0. But consanguinity implies that if G_{i} is obtained from G_{i−1} by the addition of more than two ears, then by the proof of Theorem 1 in [3] there is a longer ear decomposition of G_{i}. This contradiction shows that the ear decomposition of G is permissible. That the number of 2-ear additions meets the Naddef-Pulleyblank bound follows from the fact that dim A(G) = n. We have therefore established that the existence, in a 1-extendable graph G, of a permissible ear decomposition such that the number of 2-ear additions meets the Naddef-Pulleyblank bound is equivalent to the existence of a consanguineous evolutionary basis for A(G).

In this connection the following theorem is also of interest.

Theorem 3 Any finite-dimensional vector space over ZZ_{2} (with addition given by symmetric difference) has an evolutionary basis.

Proof: Let {S_{1}, S_{2}, …, S_{n}} be a basis for a finite-dimensional vector space over ZZ_{2}. We may assume that S_{1} has an element that does not appear in S_{i} for any i > 1, for otherwise we may choose s ∈ S_{1} and replace S_{i} by S_{i} + S_{1} for each i > 1 such that s ∈ S_{i}. The n resulting vectors are linearly independent. Proceeding inductively, we may assume that

S_{i} ⊈ ⋃_{j=i+1}^{n} S_{j}  (3)

for each i < n. We may also assume that S_{n} ∩ S_{i} ≠ ∅ for all i < n, for otherwise we may replace S_{i} by S_{i} + S_{n}. Note again that the n resulting vectors are linearly independent, and moreover that they satisfy (3). The required evolutionary ordering for the resulting basis is (S_{n}, S_{n−1}, …, S_{1}). □

In this paper we therefore propose to study evolutionary families. In particular we concentrate on sufficient conditions for a family to be evolutionary.

2 Evolutionary Families

Let S be a finite family of subsets of a finite set S. We derive necessary conditions and sufficient conditions for S to be evolutionary. Trivially S is evolutionary if |S| ≤ 1, but if |S| > 1 and ∅ ∈ S then S is not evolutionary. Accordingly we shall assume henceforth that |S| > 1 and that the elements of S are non-empty. Clearly the components of any evolutionary ordering must be distinct. Hence we may also assume that S has no repeated elements (elements of multiplicity greater than 1). We may therefore refer to S as a set, rather than as a family, though we sometimes retain the latter terminology for variety. A further observation is that at most one element of an evolutionary family can be of cardinality 1, and we may assume that S satisfies this condition also.

Let S be a finite set of subsets of a finite set. Suppose that ⋃ T ∩ ⋃(S − T ) ≠ ∅ for each nonempty proper subset T of S . Then we say that S is connected. Connectedness is clearly another requirement of an evolutionary family. The next result is slightly less trivial.

Theorem 4 Let S be a finite connected family of sets. Suppose that each member of S has cardinality no greater than 2. Then S is evolutionary if and only if it is linearly independent.

Proof: We represent S by a simple graph G whose vertices are the members of ⋃ S, distinct vertices being adjacent if and only if both are found in a single member of S. If a (unique) member of S is of cardinality 1, then its unique element is considered to be a distinguished vertex of G. The connectedness of S implies that of G. The family S is evolutionary if and only if there is a sequence (G_{1}, G_{2}, …, G_{n}) of subgraphs of G satisfying the following conditions:

• G_{1} consists of a single vertex of G (the distinguished vertex, if possible);

• for each i > 1 the graph G_{i} has an edge e_{i}, joining a vertex of ∪_{j=1}^{i−1}V G_{i} to a vertex of V G − ∪_{j=1}^{i−1}V G_{i}, such that EG_{i} = EG_{i−1} ∪ {e_{i}} and V G_{i} = V G[EG_{i−1} ∪ {e_{i}}];

• G_{n} = G.

Since G is connected, such a sequence exists if and only if G is a tree. This condition is equivalent to a lack of circuits, and therefore to the linear independence of S. □

Further progress can be made by the introduction of the concepts of backward evolutionary families and forward evolutionary families. An ordering of a finite family S of subsets of a finite set S is backward evolutionary or forward evolutionary if it satisfies condition (1) or condition (2), respectively, of Definition 1. The family is backward evolutionary or forward evolutionary if it has a backward or forward evolutionary ordering, respectively. Backward evolutionary families and forward evolutionary families can both be characterised.

Theorem 5 A finite family of subsets of a finite set is backward evolutionary if and only if it is connected.

Proof: Let S be a finite family of subsets of a finite set S. Suppose first that S is not connected. Then there exists a nonempty proper subset T of S such that ⋃ T ∩ ⋃(S −T ) = ∅. Let (S_{1}, S_{2}, …, S_{n}) be an ordering of S. Without loss of generality we may suppose that S_{1} ∈ T . Since S − T ≠ ∅, there exists a smallest integer i > 1 such that S_{i} ∉ T . Then S_{i} ∩ ⋃_{j=1}^{i−1} S_{j} = ∅, so that the ordering, and hence the family, is not backward evolutionary.

If S is connected, we construct a backward evolutionary ordering inductively. First, choose any element S_{1} of S. Next, assume that (S_{1}, S_{2}, …, S_{i}) is a backward evolutionary ordering of a nonempty proper subfamily of S. Since S is connected, there exists S_{i+1} ∈ S − {S_{1}, S_{2}, …, S_{i}} such that

S_{i+1} ∩ ⋃_{j=1}^{i} S_{j} ≠ ∅.

Then (S_{1}, S_{2}, …, S_{i+1}) is a backward evolutionary ordering of a subfamily of S. Hence S is backward evolutionary, by induction. □

Theorem 6 A finite family S of subsets of a finite set S is forward evolutionary if and only if each nonempty subfamily T of S contains an element T such that

T ⊈ ⋃(T − {T }).

Proof: Suppose there is a nonempty subfamily T of S such that each T ∈ T is a subset of ⋃(T − {T }). Let (S_{1}, S_{2}, …, S_{n}) be an ordering of S. There is a largest integer i such that S_{i} ∈ T . Since S_{i} ⊆ ⋃(T − {S_{i}}), we have S_{i} ∩ (S − ⋃_{j=1}^{i−1} S_{j}) = ∅, so that the ordering, and hence the family, is not forward evolutionary.

Conversely, suppose that every nonempty subfamily T of S contains a set T such that T ⊈ ⋃(T − {T }). We construct a forward evolutionary ordering inductively. Let n = |S|, and choose an element S_{n} of S such that S_{n} ⊈ ⋃(S − {S_{n}}). Next, suppose that (S_{n−i}, S_{n−i+1}, …, S_{n}) is an ordering of a nonempty proper subfamily T of S and satisfies the condition that

S_{j} ⊈ ⋃(S − {S_{j}, S_{j+1}, …, S_{n}})  (4)

for each j such that n − i ≤ j ≤ n. By hypothesis there exists S_{n−i−1} ∈ S − T such that

S_{n−i−1} ⊈ ⋃(S − {S_{n−i−1}, S_{n−i}, …, S_{n}}).

We now have (4) holding for each j such that n − i − 1 ≤ j ≤ n. Proceeding inductively, we obtain a forward evolutionary ordering (S_{1}, S_{2}, …, S_{n}). □

Unfortunately a family may be both forward and backward evolutionary without being evolutionary. For example, the family

{{1}, {2, 5}, {1, 2, 3, 5}, {1, 2, 3, 4}}

has forward evolutionary ordering

({1}, {2, 5}, {1, 2, 3, 5}, {1, 2, 3, 4})

and backward evolutionary ordering

({1}, {1, 2, 3, 4}, {1, 2, 3, 5}, {2, 5})

but is not evolutionary.

A family is said to be pairwise adjacent if any two of its members meet. Clearly any ordering of a pairwise adjacent family is backward evolutionary. Consequently a pairwise adjacent family is evolutionary if and only if it is forward evolutionary.

Let S be a finite set and S a family of subsets of S whose union is S. For each s ∈ S we define i_{S}(s) to be the collection of elements of S containing s. Thus i_{S} is a function from S into P(S), the power set of S. Note also that i_{S}(s) ≠ ∅ for each s ∈ S, since ⋃ S = S. We define I_{S}(S) = |i_{S}[S]|. If S is evolutionary then there must be an s ∈ S such that |i_{S}(s)| = 1, as the last set in an evolutionary ordering must contain such an s. In other words, there exists a unique set X ∈ S such that s ∈ X. Thus {X} ∈ i_{S}[S]. We infer that if m is the number of sets T in S for which {T } ∈ i_{S}[S] then m > 0.

Theorem 7 Let S be a finite set and S a family of n subsets of S whose union is S. Let m be the number of sets T ∈ S such that {T } ∈ i_{S}[S].

(a) If m = n and I_{S}(S) ≥ 2^{n} − 2^{n−2}, then S is evolutionary.

(b) If 0 < m < n and I_{S}(S) ≥ 2^{n} − min{2^{n−2}, (n − m)2^{m}}, then S is evolutionary.

Proof: Note first that if I_{S}(S) ≥ 2^{n} − 2^{n−2} then S is pairwise adjacent. Indeed, choose X, Y ∈ S. Of the 2^{n} − 1 nonempty subsets of S, 2^{n−2} contain both X and Y. The hypothesis concerning I_{S}(S) shows that at least one of these is the image under i_{S} of some s ∈ S. In other words, X ∈ i_{S}(s) and Y ∈ i_{S}(s). It follows that s ∈ X ∩ Y. Hence S is pairwise adjacent. It remains only to show that S is forward evolutionary under the hypotheses of the theorem.

(a) If m = n then any ordering of S is forward evolutionary.

(b) Suppose that 0 < m < n. Let T be a nonempty subfamily of S. According to Theorem 6 we must find T ∈ T such that T ⊈ ⋃(T − {T }). Certainly an element T of T satisfies this property if there exists s ∈ T such that |i_{T} (s)| = 1, for then s ∉ ⋃(T − {T }). We may therefore assume that |i_{T} (s)| ≥ 2 for each s ∈ ⋃ T . Thus T contains none of the m sets X ∈ S for which {X} ∈ i_{S}[S]. It follows that |T | = n − r for some integer r such that m ≤ r < n. Since there are 2^{r} subfamilies of S − T , there are (n − r)2^{r} subfamilies of S which contain exactly one element of T . Therefore there are at least (n − m)2^{m} such subfamilies, as

(n − (r + 1))2^{r+1} − (n − r)2^{r} = 2^{r}(n − r − 2) ≥ 0

whenever r ≤ n − 2. The hypothesis concerning I_{S}(S) implies that at least one of these subfamilies is the image under i_{S} of some s ∈ S, for otherwise

I_{S}(S) ≤ 2^{n} − 1 − (n − m)2^{m}.

Thus there is a unique member T of T containing s. Hence s ∉ ⋃(T − {T }), so that T has the required property. □

The following lemma enables us to derive a corollary of Theorem 7.

Lemma 1 Let S be a finite family {S_{1}, S_{2}, …, S_{n}} of subsets of a finite set S, and let R ⊆ S. Let

S|_{R} = {S_{1} ∩ R, S_{2} ∩ R, …, S_{n} ∩ R}.

If

(S_{1} ∩ R, S_{2} ∩ R, …, S_{n} ∩ R)

is an evolutionary ordering of S|_{R}, then (S_{1}, S_{2}, …, S_{n}) is an evolutionary ordering of S.

Proof: The result is an immediate consequence of the inclusions

S_{i} ∩ R ∩ ⋃_{j=1}^{i−1}(S_{j} ∩ R) ⊆ S_{i} ∩ ⋃_{j=1}^{i−1} S_{j}

and

S_{i} ∩ R ∩ (R − ⋃_{j=1}^{i−1}(S_{j} ∩ R)) ⊆ S_{i} ∩ (S − ⋃_{j=1}^{i−1} S_{j})

for all i > 1. □

Theorem 8 Let S be a finite set and S a family of n subsets of S whose union is S. If n ≥ 3 and I_{S}(S) ≥ 2^{n} − n then S is evolutionary.

Proof: Suppose first that n ≥ 4. In the notation of Theorem 7 we then have m > 0 (since n of the 2^{n} − 1 nonempty subsets of S are of cardinality 1), 2^{n−2} ≥ n and 2^{m}(n − m) ≥ 2(n − 1) > n if m < n. In this case the theorem follows immediately from Theorem 7.

Suppose therefore that n = 3. We must show that if I_{S}(S) ≥ 5 then S is evolutionary. Let S = {X, Y, Z}. Since ⋃ S = S we infer that i_{S}(s) ≠ ∅ for each s ∈ S. In other words, the members of i_{S}[S] account for at least five of the seven nonempty subsets of S. Without losing generality we may assume that the complement in P(S) − {∅} of i_{S}[S] is a subset of one of the following:

(a) {{X}, {Y }},

(b) {{X}, {X, Y }},

(c) {{X}, {Y, Z}},

(d) {{X}, {X, Y, Z}},

(e) {{X, Y }, {Y, Z}},

(f) {{X, Y }, {X, Y, Z}}.

In cases (a) - (c) and (e) we have {{Z}, {X, Z}, {X, Y, Z}} ⊂ i_{S}[S] and so we may choose:

a ∈ Z − (X ∪ Y),
b ∈ (X ∩ Z) − Y,
c ∈ X ∩ Y ∩ Z.

Thus if R = {a, b, c} we find that

({c}, {b, c}, {a, b, c})

is an evolutionary ordering of the family {X ∩ R, Y ∩ R, Z ∩ R}. Similarly in the remaining cases we have {{Y }, {Y, Z}, {X, Z}} ⊂ i_{S}[S] and may choose:

a ∈ Y − (X ∪ Z),
b ∈ (Y ∩ Z) − X,
c ∈ (X ∩ Z) − Y.

Once again, putting R = {a, b, c} we obtain the evolutionary ordering

({c}, {b, c}, {a, b})

of the family {X ∩ R, Y ∩ R, Z ∩ R}. In all cases an appeal to Lemma 1 therefore completes the proof. □

Theorem 8 does not hold for n = 2. For example, let S = {x, y} and S = {{x}, {y}}, which is not evolutionary. However i_{S}(x) = {{x}} and i_{S}(y) = {{y}}. Hence i_{S}[S] = {{{x}}, {{y}}}, so that I_{S}(S) = 2.

Observe also that Theorem 8 is the best possible result of this sort. Indeed, if I_{S}(S) = 2^{n} − n − 1 then it may be that m = 0. If so, S cannot be evolutionary.

As an example, we use Theorem 8 to confirm that the Petersen graph satisfies the theorem of Carvalho, Lucchesi and Murty. Let P denote the Petersen graph, take S = EP and let S be a basis for A(P). Thus |S| = 4. We can verify that S is evolutionary by showing that I_{S}(S) ≥ 12. In fact it is easy to show that I_{S}(S) = |EP | = 15. Observe that for any two distinct edges e and f there is an alternating circuit that contains e but not f. (This fact is easy to check, as any alternating circuit passing through e misses some edges at a distance of 1, 2 and 3 from e.) Consequently distinct edges have distinct images under i_{S}, and so this function is injective. Hence I_{S}(S) = |EP |, as claimed. It follows by Theorem 8 that any basis for A(P) is evolutionary. Thus P indeed satisfies Theorem 2.

3 Dendritic Families

In this section we introduce a special kind of family which we describe as dendritic, and we show that this property is sufficient for the family to be evolutionary.

Let S be a finite family of subsets of a finite set S, and let a, b ∈ S. (Recall our earlier assumption that ∅ ∉ S.) An evolutionary path in S between a and b is defined as a minimal connected subset of S whose union contains a and b.

Theorem 9 A finite family S of subsets of a finite set S whose union is S is connected if and only if there is an evolutionary path in S between any two members of S.

Proof: If S is a finite connected family of subsets of a finite set S whose union is S and a, b ∈ S, then there is certainly an evolutionary path in S between a and b.

Conversely let us suppose that S is a finite family of subsets of a finite set S whose union is S and that there exists an evolutionary path in S between any two members of S. Let A be a nonempty proper subset of S, and suppose that ⋃ A ∩ ⋃(S − A) = ∅. Choose a ∈ ⋃ A and b ∈ ⋃(S − A). By hypothesis there is an evolutionary path P in S between a and b. Let T = P ∩ A. Note that T ≠ ∅, since a belongs to a set in A and therefore not to a set in S − A. Similarly T ≠ P. Since P is connected, ⋃ T ∩ ⋃(P − T ) ≠ ∅. But ⋃ T ⊆ ⋃ A and ⋃(P − T ) ⊆ ⋃(S − A), and so we reach the contradiction that ⋃ A ∩ ⋃(S − A) ≠ ∅. Hence S is connected. □

Lemma 2 Let S be a finite family of subsets of a finite set S, and let a, b, c ∈ S. If there exist an evolutionary path in S between a and b and another between b and c, then there is an evolutionary path in S between a and c.

Proof: Let P be an evolutionary path between a and b and let Q be an evolutionary path between b and c. We may assume that c ∉ ⋃ P, for otherwise the lemma holds. Let T = P∪Q. It suffices to prove T connected. Choose a nonempty proper subset A of T . Let R = P ∩A. If ∅ ⊂ R ⊂ P, then the connectedness of P implies that ⋃ R ∩ ⋃(P − R) ≠ ∅. But ⋃ R ⊆ ⋃ A since R ⊆ A, and similarly ⋃(P − R) ⊆ ⋃(T − A). Hence ⋃ A ∩ ⋃(T − A) ≠ ∅. Similarly ⋃ A ∩ ⋃(T − A) ≠ ∅ if Q ∩ A is a nonempty proper subset of Q. We may therefore assume without loss of generality that A = P. Then either b ∈ ⋃ A ∩ ⋃(T − A) or b belongs to a member of P ∩ Q. In the latter case we have ∅ ⊂ Q ∩ P ⊂ Q since c ∈ ⋃ Q − ⋃ P. In both cases we conclude that T is connected. □

We say that a finite family D of subsets of a finite set S is dendritic if the following conditions hold:

1. |D| > 1 for each D ∈ D;

2. any two distinct elements of ⋃ D have a unique evolutionary path in D between them.

Theorem 10 Let D be a member of a dendritic family D. Then D has an evolutionary ordering whose first component is D.

Proof: Let E be a largest subset of D that has an evolutionary ordering whose first component is D. We must show that E = D.

Suppose that E ⊂ D. By condition 2 and Theorem 9 we see that D is connected. Therefore ⋃ E ∩ ⋃(D − E) ≠ ∅. Hence there exists a set E ∈ D − E which meets a set A ∈ E. Thus we may choose a ∈ A ∩ E. Suppose that E − {a}, which is nonempty by condition 1, also meets a set B ∈ E, and choose b ∈ B ∩ (E − {a}). Note that {E} is an evolutionary path between a and b. But since E is evolutionary and therefore connected, some subset of E is also an evolutionary path between a and b. As these evolutionary paths are distinct, we have a contradiction to condition 2. Therefore E − {a} does not meet any set in E. We deduce that E ∪ {E} is an evolutionary family. This contradiction to the choice of E completes the proof. □

A family

A = {A_{1}, A_{2}, …, A_{n}}

is called an ancestor of a family

S = {S_{1}, S_{2}, …, S_{n}}

if ∅ ⊂ A_{i} ⊆ S_{i} for each i. For each i we say that A_{i} is the ancestor of S_{i}. If A_{i} ⊂ S_{i} for at least one i, then the ancestor A is proper. A family is said to be radical with respect to a given property if no proper ancestor also satisfies the property.

Theorem 11 Let S be a backward and forward evolutionary family of subsets of a finite set S. Suppose that each set in S has cardinality greater than 1. Then S has a dendritic ancestor.

Proof: If |S| = 1 then S is dendritic. We may therefore assume that |S| > 1 and that the theorem holds for all forward and backward evolutionary families, of cardinality less than |S|, whose elements are sets of cardinality greater than 1. We must find a dendritic ancestor for S.

Since S is forward evolutionary, it has a forward evolutionary ordering whose last component E necessarily contains an element belonging to no set in S − {E}. Choose a backward evolutionary ordering for S in which E appears as late as possible. Then the set R of elements of S appearing before E constitutes a maximal connected subfamily of S − {E}. Certainly R is backward evolutionary. Since S is forward evolutionary, so is R. As |R| < |S| it follows that R has a dendritic ancestor, C.

Since S, being backward evolutionary, is connected but R is a maximal connected subfamily of S − {E}, it follows that ⋃ R ∩ E ≠ ∅. (Suppose ⋃ R ∩ E = ∅. Since R ⊂ S and S is connected, there must exist S ∈ S − R such that ⋃ R ∩ S ≠ ∅. Thus S ≠ E. Moreover R ∪ {S} is backward evolutionary and hence a connected subfamily of S − {E}, in contradiction to the maximality of R.) Choose e ∈ ⋃ R ∩ E, and define E′ = (E − ⋃ R) ∪ {e}. Thus E′ ∩ ⋃ R ≠ ∅, and |E′| > 1 since E has an element belonging to no other member of S. Moreover E′ ⊆ E.

Let S′ = (S − {E}) ∪ {E′}. Since E′ ∩ ⋃ R ≠ ∅ and E − E′ ⊂ ⋃ R, it follows that S′ has a backward evolutionary ordering obtained by replacing E with E′, and is therefore connected.

We show next that S′ − R is connected. Choose a nonempty proper subset T of S′ − R. Without loss of generality we may assume that E′ ∉ T . We must show that

⋃ T ∩ ⋃(S′ − (R ∪ T )) ≠ ∅.

Since S′ is connected, we may choose x ∈ ⋃ T ∩ ⋃(S′ − T ). If x ∉ ⋃ R then x ∈ ⋃ T ∩ ⋃(S′ − (R ∪ T )), as required. Suppose therefore that x ∈ ⋃ R. Since x ∈ ⋃ T , we also have x ∈ ⋃(S′ − R), and it suffices to show that x ∈ ⋃(S′ − (R ∪ T )). But R is a maximal connected subfamily of S′ − {E′}, and so ⋃ R ∩ ⋃(S′ − R) ⊆ E′. Hence x ∈ E′, so that x ∈ ⋃(S′ − (R ∪ T )), as required.

Thus S′ − R is backward evolutionary. It is also forward evolutionary, for S − R has a forward evolutionary ordering with last component E since S − R ⊂ S, and a forward evolutionary ordering for S′ − R is obtained by replacing E with E′. Since |E′| > 1 and |S′ − R| = |S − R| < |S|, we may apply the inductive hypothesis to obtain a dendritic ancestor D of S′ − R. Note also that

⋃ R ∩ ⋃(S′ − R) = {e}.

We now introduce three cases, defining an ancestor A of S in each.

Case I: If e ∈ ⋃ C ∩ ⋃ D, let C′ = C, D′ = D and A = C′ ∪ D′.

Case II: Suppose that only one of ⋃ C, ⋃ D contains e. Without loss of generality suppose that e ∈ ⋃ D. Choose C ∈ C such that C is the ancestor of a member of R that contains e, and define C′ = C ∪ {e} and C′ = (C − {C}) ∪ {C′}. Let D′ = D and A = C′ ∪ D′.

Case III: Suppose that neither ⋃ C nor ⋃ D contains e. Choose C ∈ C such that C is the ancestor of a member of R that contains e, and define C′ = C∪{e} and C′ = (C−{C})∪{C′}. Similarly choose D ∈ D such that D is the ancestor of a member of S′ − R that contains e, and define D′ = D ∪ {e} and D′ = (D − {D}) ∪ {D′}. Let A = C′ ∪ D′.

In every case A is an ancestor of S whose elements are sets of cardinality greater than 1. It remains to prove that any two distinct elements a and b in ⋃ A have a unique evolutionary path in A between them. Again we divide the argument into cases.

Case I: Suppose first that {a, b} ⊆ ⋃ C. Then there is a unique evolutionary path P in C between a and b. If C ∈ P then we define P′ = (P − {C}) ∪ {C′}; otherwise let P′ = P. Then P′ is an evolutionary path in C′ between a and b. (Suppose that some proper subset Q of P′ were to satisfy the conditions that a ∈ ⋃ Q, b ∈ ⋃ Q and Q is backward evolutionary. The minimality of P would imply that C′ ∈ Q, so that C′ ∈ P′ and C ∈ P. But then (Q − {C′}) ∪ {C} would be backward evolutionary since e ∉ ⋃(Q − {C′}). This result would contradict the minimality of P.)

Now let Q′ be any evolutionary path in A between a and b. Since ⋃ D′ ∩ ⋃ C′ = {e}, we have Q′ ⊆ C′ by the minimality of Q′. If C′ ∉ P′∪Q′ then P′ = Q′ = P by the uniqueness of P. Without loss of generality we may therefore assume that C′ ∈ Q′. It follows that C ∉ C′. Moreover (Q′ − {C′}) ∪ {C} is backward evolutionary since e ∉ ⋃(Q′ − {C′}). Suppose some proper subset T of (Q′ − {C′}) ∪ {C} were to satisfy the conditions that a ∈ ⋃ T , b ∈ ⋃ T and T is backward evolutionary. The minimality of Q′ would imply that C ∈ T , but then (T − {C}) ∪ {C′} would be backward evolutionary, in contradiction to the minimality of Q′. We infer that (Q′ − {C′}) ∪ {C} is an evolutionary path between a and b.Hence (Q′−{C′})∪{C} = P by the uniqueness of P, so that Q′ = (P −{C})∪{C′}. Since C ∉ C′ we have P′ ≠ P, and so C′ ∈ P′ by the uniqueness of P. Thus P′ = (P −{C})∪{C′} = Q′. Hence P′ is unique, as required.

The argument is similar if {a, b} ⊆ ⋃ D.

Case II: Next, suppose that a ∈ ⋃ C and b = e. We may assume that e ∈ C′, for otherwise Case I applies. Since |C| > 1, there exists c ∈ C − {a}. There is a unique evolutionary path P in C between a and c, and c belongs to a unique set P in P by the minimality of P. Define P′ = (P − {C}) ∪ {C′} if P = C, and let P′ = P ∪ {C′} otherwise. Then P′ is an evolutionary path in C′ between a and e. (Suppose that some proper subset Q of P′ were to satisfy the conditions that a ∈ ⋃ Q, e ∈ ⋃ Q and Q is backward evolutionary. Then C′ ∈ Q since e ∈ ⋃ Q, so that (Q − {C′}) ∪ {C} would be backward evolutionary. This result would contradict the minimality of P if C ∈ P, and the uniqueness of P otherwise since |Q| ≤ |P′| − 1 = |P|.)

Now let Q′ be any evolutionary path in A between a and e. Then Q′ ⊆ C′ by the minimality of Q′. Moreover Q′ − {C′} and (Q′ − {C′}) ∪ {C} are backward evolutionary. In fact, if c ∈ ⋃(Q′ − {C′}) then it follows from the minimality of Q′ that Q′ − {C′} is an evolutionary path in C between a and c. In this case Q′ − {C′} = P by the uniqueness of P, so that Q′ = P ∪{C′}. Suppose therefore that c ∉ ⋃(Q′−{C′}). Then (T −{C})∪{C′} is backward evolutionary for any backward evolutionary, proper subset T of (Q′ − {C′}) ∪ {C} such that {a, c} ⊆ ⋃ T . This contradiction to the minimality of Q′ shows that (Q′ − {C′}) ∪ {C} is an evolutionary path in C between a and c. Hence (Q′ − {C′}) ∪ {C} = P by the uniqueness of P, so that Q′ = (P − {C}) ∪ {C′}. In both cases Q′ is unique.

The argument is similar if a ∈ ⋃ D and b = e.

Case III: Without loss of generality we may now assume that a ∈ ⋃ C − {e} and b ∈ ⋃ D − {e}. By Case II there exist a unique evolutionary path P in C′ between a and e and a unique evolutionary path Q in D′ between e and b. Then P ∪ Q is the unique evolutionary path in A between a and b, since ⋃ C′ ∩ ⋃ D′ = {e}.

We have now confirmed that A is the required dendritic ancestor of S. □

Corollary 1 Let S be a finite family which is radical with respect to the property of being forward and backward evolutionary. Suppose also that each member of S is of cardinality greater than 1. Then S is dendritic.

Proof: Otherwise S has a dendritic ancestor, by Theorem 11. Being evolutionary by Theorem 10, this ancestor contradicts the assumption that S is radical. □

Corollary 2 Let S be a finite family of nonempty sets that is forward and backward evolutionary and contains at most one set of cardinality 1. Then S has an evolutionary ancestor.

Proof: The corollary follows immediately if no set in S is of cardinality 1. In the remaining case, let X be the set in S of cardinality 1, and let E = S − {X} and X = {x}. Then E is forward and backward evolutionary and each set in E is of cardinality greater than 1. Thus, by Theorem 11, E has a dendritic ancestor A.

Case I: If x ∈ ⋃ A, then by Theorem 10 there is an evolutionary ordering of A whose first component contains x. It follows that {X} ∪ A is an evolutionary ancestor of S.

Case II: If x ∉ ⋃ A, then there is a set Y in A which is a subset of a set S in S containing x. Define Y′ = Y ∪ {x} and let A′ = (A − {Y }) ∪ {Y′}. Then A′ is an ancestor of S − {X} with an evolutionary ordering whose first component is Y′. It follows that A′ ∪ {X} is an ancestor of S with an evolutionary ordering whose first two components are X and Y′. □

For example, the family {{1}, {2, 5}, {1, 2, 3, 5}, {1, 2, 3, 4}}, which we have shown to be forward and backward evolutionary, has an ancestor with evolutionary ordering ({1}, {1, 2}, {2, 3}, {2, 5}).

References

[1] C. P. Bonnington, C. H. C. Little, The Foundations of Topological Graph Theory, Springer, New York, 1995.

[2] M. H. Carvalho, C. L. Lucchesi, U. S. R. Murty, Ear decompositions of matching covered graphs, technical report, University of Waterloo, 1998.

[3] C. H. C. Little, F. Rendl, An algorithm for the ear decomposition of a 1-factor covered graph, J. Austral. Math. Soc. A46 (1989), 296–301.

[4] L. Lovász, M. D. Plummer, Matching Theory, Akadémiai Kiadó, Budapest, 1986.

[5] D. J. Naddef, W. R. Pulleyblank, Ear decompositions of elementary graphs and GIF_{2}- rank of perfect matchings, Ann. Disc. Math. 16 (1982), 241–260.