# Gallai-Colorings of Triples and 2-Factors ofℬ3

Authors: Lynn Chua; András Gyárfás; Chetak Hossain
Journal: International Journal of Combinatorics
 (2013)

---

## Abstract

A coloring of the edges of ther-uniform complete hypergraph is a Gr-coloring if there is no rainbow simplex; that is, every set of r+1 vertices contains two edges of the same color. The notion extends G2-colorings which are often called Gallai-colorings and originates from a seminal paper of Gallai. One well-known property of G2-colorings is that at least one color class has a spanning tree. J. Lehel and the senior author observed that this property does not hold for Gr-colorings and proposed to study fr(n), the size of the largest monochromatic component which can be found in every Gr-coloring of Knr, the complete r-uniform hypergraph. The previous remark says that f2(n)=n, and in this note, we address the case r=3. We prove that ⌈(n+3)/2⌉≤f3(n)≤⌈4n/5⌉, and this determines f3(n) for n<7. We also prove that f3(7)=6 by excluding certain 2-factors from the middle layer of the Boolean lattice on seven elements.


---

## Body

## 1. Introduction

Studying edge colorings of complete graphs without rainbow triangles (no triangles colored with distinct colors) originates from a famous paper of Gallai [1]; we will refer to such colorings as Gallai-colorings or G2-colorings. A well-known property of G2-colorings is that the edges of some color class span a connected subgraph containing all vertices. A natural extension of the concept is the Gr-coloring, of Knr, the complete r-uniform hypergraph on n vertices. In a Gr-coloring the requirement is that no Kr+1r is colored with r+1 distinct colors; that is, there is no rainbow simplex. For r≥3, Gr-colorings of Kn3 do not necessarily contain spanning connected color classes, but they must contain large ones. To define how large, let fr(n) be the size of the largest monochromatic component which can be found in every Gr-coloring of Knr. In terms of this function, f2(n)=n, and in this note we address f3(n).Theorem 1.
⌈
(
n
+
3
)
/
2
⌉
≤
f
3
(
n
)
≤
⌈
4
n
/
5
⌉.Proof.
The upper bound (an unpublished note of the senior author and J. Lehel) follows from taking first theG3-coloring of K53 with five colors, where the vertex set is {1,2,3,4,5}, and the edges i, i+1, i+2 and i, i+2, i+3 are colored with i (using (mod 5) arithmetic). This coloring can be “blown up” by replacing each vertex i by a set Ai so that the five sets have sizes that differ by at most one and defining the following straightforward extension of the original 5-coloring. Triples with vertices from three different Ai are colored according to the color of the triple of their indices. Triples inside Ai and triples in Ai∪Ai+1 or in Ai∪Ai+2 (with at least one vertex in each) are colored with color i.
The lower bound follows from the observation that every 4-set must contain two 3-sets of the same color. Thus the color of some 3-setT is repeated on another triple inside at least
(1)2(n2)(n3)=n-32
4-sets containing T. This means that the monochromatic component containing T has at least (n-3)/2+3 vertices.In fact, for oddn>3, the proof of the lower bound in Theorem 1 gives a condition for equality in terms of the bipartite graph ℬ4,3n defined by the inclusions of the 4- and 3-element sets of {1,2,…,n}.  A (p,q)-factor in a bipartite graph [A,B] is a subgraph with
(2)d(v)={pifv∈A,qifv∈B,
where d(v) is the degree of vertex v.Corollary 2.
If the lower bound of Theorem1 is sharp for some odd n≥5 then there is a (2,(n-3)/2)-factor F in ℬ4,3n, such that the union of the triples and quadruples in every component of F has at most (n+3)/2 elements.Theorem1 implies that f3(4)=f3(5)=4 and f3(6)=5 but gives only f3(7)∈{5,6}. Notice that, for n=5, the upper bound construction of Theorem 1 is a (2, 1)-factor in ℬ4,35 required in Corollary 2, consisting of the shifts of the 3-vertex component 1234, 123, 134 modulo 5. Is it possible that for some n>5 there is a (2,(n-3)/2)-factor providing a better upper bound for f3(n)? The first case to consider is ℬ3=ℬ4,37, the “middle-layer graph” in the boolean lattice on seven elements. To decide whether f3(7)=5, we will determine all possible 2-factors required by Corollary 2. In Lemma 3 we show that these are 2-factors in ℬ3 whose components are 6-, 8-, or 10-cycles of the following type which we call a 𝒞-factor:(i)
C6=C6(a,b;c,d,e) the 6-cycle abc, abcd, abd, abde, abe, abce, abc,(ii)
C8=C8(a;bcde) the 8-cycle abc, abcd, acd, acde, ade, adeb, aeb, aebc, abc,(iii)
C10=C10(abcde) the 10-cycle abc, abcd, bcd, bcde, cde, cdea, dea, deab, eab, eabc, abc,where {a,b,c,d,e}⊂{1,2,…,7}. It is worth mentioning that the cycles of a 𝒞-factor can be considered as subdivisions of certain triangles, quadrangles, and pentagons of the Johnson graph J(7,3), where J(n,3) (sometimes referred to as the tetrahedral graph) is the graph whose vertices are the triples of an n-element set and edges are between triples intersecting in two vertices. The speciality of these cycles is that the triples (and quadruples) are among five elements (a,b,c,d, and e). The 2-factors of the middle layer graph are investigated before, primarily because of the middle level (or revolving door) conjecture; see [2] and its references.Lemma 3.
f
3
(
7
)
=
5 if and only if ℬ3 has a 𝒞-factor.Proof.
Ifℬ3 has a 𝒞-factor, we have a G3-coloring of K53 obtained by coloring the 3-sets with the same color if and only if they are in the same cycle in the 𝒞-factor. The triples of each cycle determine a monochromatic component with five vertices; hence f3(7)≤5, and together with the lower bound of Theorem 1, we get f3(7)=5.
Conversely, suppose thatf3(7)=5, and consider the G3-coloring of K73 with all monochromatic components having at most five vertices. Let B⊂ℬ3 be the bipartite graph defined by selecting two 3-sets of the same color from each 4-element subset of {1,2,…,7}. The graph B must be 2-regular, otherwise some 3-set, say in color red, would be selected into at least three 4-sets, resulting in a red component of at least six vertices. Thus B is a 2-factor in ℬ3, and its components are cycles. But ℬ3 contains no C4 since two 4-sets can share at most one 3-set. Also, ℬ3 cannot have a Cn component with n≥12; otherwise the corresponding coloring of K53 has a monochromatic component with more than five vertices, since there are only five 4-sets on five elements. Thus the components of B are elements of {C6,C8,C10}. However, these cycles have to form subdivisions of {C3,C4,C5} in the Johnson graph J(5,3), such that the union of triples on the edges of a cycle forms different 4-sets. This means that the edges of C∈{C3,C4,C5} which are to be subdivided must be in different main cliques of J(5,3), where a main clique K4 is the complete subgraph of J(5,3) determined by the triples of {1,2,3,4,5}-{i} for some i∈{1,2,3,4,5}. The edge set of J(5,3) is partitioned into five main cliques, and we can label the edges in each main clique by i, such that C consists of edges with different labels. If two edges i, j meet, then the corresponding 3-set is {1,2,3,4,5}-{i,j}. For a C3 with edges labeled 3, 4, and 5, the corresponding 3-sets are 123, 124, and 125. One can similarly check for C4 and C5 that the only possibilities are the cycles in the definition of the 𝒞-factor.In Sections2 and 3 we prove the following.Theorem 4.
ℬ
3 has no 𝒞-factor.Lemma3 and Theorems 1 and 4 give the following.Corollary 5.
f
3
(
7
)
=
6.Theorem4 might be true in a stronger form.Question 1.
Is there a 2-factor inℬ3 in which all cycles have length of at most 10?It is worth mentioning that, in the family of 2-factors constructed in [2], all components are cycles with length divisible by 14; thus it does not answer Question 1.The proof of Theorem4 is based on properties of graphs shown in Figure 2. They are the graphs on seven vertices having 11, 10, or 9 edges with the property that every set of three vertices contains at least one edge (complements of triangle-free graphs that are close to the extremal Turán graphs). We need to analyze star-partitions xS3+yS4+zS5 of K73, where the star Si is the hypergraph having i triples containing two fixed vertices, called the base. Note that K73 is an interesting object to decompose. For example, K73 can be partitioned into 5 “tight cycles” (consecutive triples in a cyclic permutation of V(K73)) but cannot be partitioned into 5 Fano planes. In fact, K73 does not contain three edge disjoint Fano planes (Cayley [3]). However, K73 can be partitioned into 6 linear hypergraphs (but not into 5) [4].Decompositions of complete hypergraphs into stars (hyperclaws) have been investigated [5, 6], and this is strongly related to our subject. In particular, the following decomposition problem is related to the case n=9. Let H be a star S4 with vertex set x1,…,x6 and with base x1x2. Define the mate of H as the 4-uniform hypergraph with the six 4-element subsets {x1,x2,xi,xj} where i,j,i≠j runs over the unordered pairs of 3, 4, 5, 6.Question 2.
Is it possible to partitionK93 into stars S4 so that their mates partition K94? (Star partition without the mate condition is possible [5].)In fact, Question2 is a very special case of the 𝒞-factor problem arising from the question whether f3(9)>6. Here 𝒞 should be the list of components of a (2, 3)-factor of ℬ4,39 that contain triples and quadruples of six elements (out of nine). Such components arise by subdividing the edges of several 3-regular subgraphs of J(6,3). Question 2 came about by considering the component of a (2, 3)-factor from the subdivision of a K4∈J(6,3). However, other components come from the subdivision of the following graphs: K2×K3, the graph obtained from K2×K3 by subdividing two edges not in a triangle and connecting the subdivision points with an edge, the cube, and the Petersen graph—we checked with a computer that this list is exhaustive. For example, the cube in J(6,3) represented by
(3)123,124,245,235,136,146,456,356
and the Petersen graph in J(6,3) represented by
(4)123,124,235,136,145,345,156,246,256,346
generate components with 8 and 10 triples (and 12 and 15 quadruples) in ℬ4,39. Thus there are five possible components of a (2, 3)-factor in 𝒞, and this probably makes it difficult to decide whether f3(9)>6.


## 2. Special 2-Factors inℬ3 and Star Decompositions of K73

We use𝒞6, 𝒞8, and 𝒞10 to denote the set of possible cycles of a 𝒞-factor with different parameter choices from {1,2,…,7} (e.g., |𝒞10|=4!(57)). Then 𝒞=𝒞6∪𝒞8∪𝒞10, and a 𝒞-factor is a 2-factor of ℬ3 such that each cycle in it belongs to 𝒞.The type of a𝒞-factor is the vector (x,y,z) where x,y, and z denote the number of cycles of 𝒞 from 𝒞6, 𝒞8, and 𝒞10, respectively. One can easily determine the possible types of a 𝒞-factor by determining the nonnegative integer solutions of 35=3x+4y+5z. There are 14 types, and we will eliminate all of them.First we reformulate the existence of a𝒞-factor as a decomposition problem of K73. We define Si, thei-star, as a 3-uniform hypergraph having i edges containing a fixed pair of vertices, called the base of the star. A star partition of Kn3 is a partition of all edges into stars; in particular Kn3=∑i=1k‍xiSi means that Kn3 is partitioned into xi copies of Si, for i=1,2,…,k. Notice that the complements of the four-element sets in the cycles of a 𝒞-factor provide a starpartition of K73. On the other hand, the three-element sets in the cycles of a 𝒞-factor also give a partition of K73 into copies of the hypergraphs H3, H4, and H5 which we call the complementary partition (H3 is isomorphic to S3, H4 has four triples containing a fixed vertex and consecutive pairs on a 4-cycle of pairs, and H5 has five consecutive triples on a 5-cycle of pairs; these are illustrated in Figure 1). These considerations lead to the following.Figure 1
Diagram of the starsSi with base fg (red) and the corresponding hypergraphs Hi (blue).Figure 2
Diagram of the possible base graphsT9, T10, T111,…, T115.Proposition 6.
ℬ
3 has a 𝒞-factor of type (x,y,z) if and only if K73 has a star partition xS3+yS4+zS5 together with the complementary partition xH3+yH4+zH5.


### 2.1. DecomposingK73 along Turán Graphs

We associate a weighted graphG, the base graph, with a star partition xS3+yS4+zS5 on K73 as follows. The vertex set of G is {1,2,…,7}, and the (x+y+z) edges are determined by the pairs of the bases of the stars in the partition. The graph obtained this way has no multiple edges because different stars must have different bases, since two stars have at least six edges. The weight of an edge e is i if e is the base of an Si.IfG is the base graph of a star partition xS3+yS4+zS5 on K73, then every triple of {1,2,…,7} contains at least one edge of G. By Turán’s theorem (complementary form), x+y+z≥9, and for x+y+z=9, x+y+z=10, the graphs G=T9 or G=T10 are unique: the vertex disjoint union of K3 and K4, with an edge in between in the case of T10.Whenx+y+z=11, easy inspection reveals five possibilities for the base graph. Let T111 be the disjoint union of K5 and K2. Then T112, T113, and T114 are disjoint unions of K3 and K4 plus two edges between them, with a common vertex in K4, a common vertex in K3, and no common vertex, respectively (see Figure 2). Finally, T115 is the disjoint union of two K3-s plus one edge between them plus four edges from the seventh vertex to the vertices of degree two (complement of K3,3 with a subdivided edge).These considerations eliminate the vectors of types (0,0,7), (2,1,5), (1,3,4), and (0,5,3) and reduce the problem to the following cases.Lemma 7.
Suppose thatℬ3 has a 𝒞-factor of type (x,y,z). Then one has on K73 a star partition with base graph G together with a complementary partition with the following parameters.  (i)
G=T9 and (x,y,z)∈{(1,8,0),(5,0,4),(4,2,3),(3,4,2),(2,6,1)}.(ii)
G=T10 and (x,y,z)∈{(5,5,0),(7,1,2),(6,3,1)}.(iii)
G∈{T11i:i∈{1,2,3,4,5}} and (x,y,z)∈{(9,2,0),(10,0,1)}.The following lemma will eliminate six types of vectors.Lemma 8.
Suppose thatℬ3 has a 𝒞-factor of type (x,y,z) with z>0. Then the base graph has a 5-cycle.Proof.
Suppose thatℬ3 has a C10 cycle, C=C10(12345), the 10-cycle 123, 1234, 234, 2345, 345, 3451, 451, 4512, 512, 5123, and 123, which generates an S5 with base edge 67. Consider the remaining five 3-sets formed from the vertices 12345 which are not in C: 124, 134, 135, 235, and 245. Observe that 124 is only contained in the 4-sets 1234, 1245, 1246, and 1247. Since 1234, 1245 are in C, then 124 must be in the same cycle as 1246 and 1247. Hence we have a cycle on the vertices 12467. Similarly, we have four other cycles on 13467, 13567, 23567, and 24567. The base edges of the five stars generated by these five cycles are, respectively, 35, 25, 24, 14, 13, which form a 5-cycle in the base graph.SinceT9, T10, and T112 do not contain 5-cycles, we have the following.Lemma 9.
Suppose thatℬ3 has a 𝒞-factor of type (x,y,z). Then one has on K73 a star partition with base graph G together with a complementary partition with the following parameters.  (i)
G=T9 and (x,y,z)=(1,8,0).(ii)
G=T10 and (x,y,z)=(5,5,0).(iii)
G∈{T11i:i∈{1,2,3,4,5}} and (x,y,z)∈{(9,2,0),(10,0,1)}.


## 2.1. DecomposingK73 along Turán Graphs

We associate a weighted graphG, the base graph, with a star partition xS3+yS4+zS5 on K73 as follows. The vertex set of G is {1,2,…,7}, and the (x+y+z) edges are determined by the pairs of the bases of the stars in the partition. The graph obtained this way has no multiple edges because different stars must have different bases, since two stars have at least six edges. The weight of an edge e is i if e is the base of an Si.IfG is the base graph of a star partition xS3+yS4+zS5 on K73, then every triple of {1,2,…,7} contains at least one edge of G. By Turán’s theorem (complementary form), x+y+z≥9, and for x+y+z=9, x+y+z=10, the graphs G=T9 or G=T10 are unique: the vertex disjoint union of K3 and K4, with an edge in between in the case of T10.Whenx+y+z=11, easy inspection reveals five possibilities for the base graph. Let T111 be the disjoint union of K5 and K2. Then T112, T113, and T114 are disjoint unions of K3 and K4 plus two edges between them, with a common vertex in K4, a common vertex in K3, and no common vertex, respectively (see Figure 2). Finally, T115 is the disjoint union of two K3-s plus one edge between them plus four edges from the seventh vertex to the vertices of degree two (complement of K3,3 with a subdivided edge).These considerations eliminate the vectors of types (0,0,7), (2,1,5), (1,3,4), and (0,5,3) and reduce the problem to the following cases.Lemma 7.
Suppose thatℬ3 has a 𝒞-factor of type (x,y,z). Then one has on K73 a star partition with base graph G together with a complementary partition with the following parameters.  (i)
G=T9 and (x,y,z)∈{(1,8,0),(5,0,4),(4,2,3),(3,4,2),(2,6,1)}.(ii)
G=T10 and (x,y,z)∈{(5,5,0),(7,1,2),(6,3,1)}.(iii)
G∈{T11i:i∈{1,2,3,4,5}} and (x,y,z)∈{(9,2,0),(10,0,1)}.The following lemma will eliminate six types of vectors.Lemma 8.
Suppose thatℬ3 has a 𝒞-factor of type (x,y,z) with z>0. Then the base graph has a 5-cycle.Proof.
Suppose thatℬ3 has a C10 cycle, C=C10(12345), the 10-cycle 123, 1234, 234, 2345, 345, 3451, 451, 4512, 512, 5123, and 123, which generates an S5 with base edge 67. Consider the remaining five 3-sets formed from the vertices 12345 which are not in C: 124, 134, 135, 235, and 245. Observe that 124 is only contained in the 4-sets 1234, 1245, 1246, and 1247. Since 1234, 1245 are in C, then 124 must be in the same cycle as 1246 and 1247. Hence we have a cycle on the vertices 12467. Similarly, we have four other cycles on 13467, 13567, 23567, and 24567. The base edges of the five stars generated by these five cycles are, respectively, 35, 25, 24, 14, 13, which form a 5-cycle in the base graph.SinceT9, T10, and T112 do not contain 5-cycles, we have the following.Lemma 9.
Suppose thatℬ3 has a 𝒞-factor of type (x,y,z). Then one has on K73 a star partition with base graph G together with a complementary partition with the following parameters.  (i)
G=T9 and (x,y,z)=(1,8,0).(ii)
G=T10 and (x,y,z)=(5,5,0).(iii)
G∈{T11i:i∈{1,2,3,4,5}} and (x,y,z)∈{(9,2,0),(10,0,1)}.


## 3. Eliminating the Remaining Types

### 3.1. (10,0,1)

Following the proof of Lemma8, we can label the 10-cycle as C10(12345), and we have 6-cycles on 12467, 13467, 13567, 23567, and 24567. In a 6-cycle, two vertices are repeated in every element. Since the five 6-cycles above contain, respectively, the 3-sets 124, 134, 135, 235, and 245, the two repeated vertices must be from these 3-sets. In particular, the 3-sets 167, 267, 367, 467, and 567 are not contained in any of these 6-cycles. There are ten 4-sets containing these five 3-sets. But each of the five 6-cycles contains one of these 4-sets. Hence there are five remaining 4-sets which contain five 3-sets, and the only possibility is that these ten elements form a 10-cycle. Then there are two 10-cycles, a contradiction.


### 3.2. (1,8,0)

LabelG=T9 so that {1,2,3,4} spans a K4 and {5,6,7} spans a K3.One of the edges of theK3 must generate the triple 567; say e=56. e must also generate the triples 156, 256, 356, and 456. But e can generate at most 4 triples, a contradiction.


### 3.3. (5,5,0)

LabelG=T10 so that {1,2,3,4} spans a K4, {5,6,7} spans a K3, and the tenth edge is (4, 5).(i)
The edgee=67 of G must be the base of a copy P1 of S4 since the triples i,6,7 for i∈[4] must be based on e. Let (w.l.o.g) 1, 2, 3, 4 be the cyclic ordering of the 4-cycle in the copy of H4 complementary to P1 (the triples in C8(5;1234)).(ii)
Consider the four base edges ofG on the 4-cycle U=1,2,3,4,1. We claim that all of them have weight 4. Suppose this is not the case, and f=ij is covered by a star P2 in S3 where i,j are consecutive on U. Observe that the triples i,j,6 and i,j,7 must be in P2. Therefore the triple M={1,2,…,7}∖{i,j,6,7} is covered by the copy of H3 complementary to P2. However, M={5,i+2,j+2} with (mod 4), addition thus it is also covered by the copy of H4 complementary to P1, a contradiction.(iii)
At this point, we know that the five base edges are of weight 4, and the rest of the edges have weight 3. In particular, 13 and 57 have weight 3, and both uniquely determine their stars inS3, namely, 135, 136, 137 and 571, 572, 573. But then the triple 246 is doubly covered by their complementary copies of H3-s, a contradiction, finishing the proof.


### 3.4. (9,2,0)

The base graphT111 cannot occur since the base edge K2 must generate 5 triples.Case 1.
Base graph isT115, the union of edge 12, the triangles 1,3,4 and 2,5,6, and the star 37, 47, 57, 67.
The base edgese=34 and f=56 must generate the triples 234, 345, 346 and 156, 356, 456, respectively. They cannot both generate S3-s because then the triple 127 would be doubly covered by their complementary H3-s.
One ofe, f, say e=34 generates an S4. Suppose first that f generates an S3. Then 13 and 14 both generate S4-s; otherwise 247 or 237 would be doubly covered by their complementary H3-s. But this is a contradiction, having at least three S4-s in the star partition. Thus f also generates an S4. Consequently, 25 and 26 both generate S3-s and their complementary H3-s contain the triples 167 and 157, respectively. However, at least one of these triples is also covered by the complementary H4 of the S4 generated by e, a contradiction.Case 2.
Base graph isT114, labeled so that {1,2,3,4} spans a K4 and {5,6,7} spans a K3, with two additional edges (4,5) (1,7).
The base edgee=23 must generate the triples 235, 236, and 237. Suppose that e generates an S3; then the complementary H3 contains the triples 145, 146, and 147. This implies that the base edges 56, 57, and 67 must all generate S4-s. Otherwise, suppose that 56 generates an S3. Since 56 must generate the triples 256 and 356, the triple 147 is in the complementary H3, and it is doubly covered by the complementary H3 of e. Similarly, if 57 and 67 generate S3-s, then the triples 146 and 145 would be doubly covered. Thus e must generate an S4.
Consider the complementaryH4 generated by e, w.l.o.g. let it be C8(1;4567). Then it contains at least two of the triples 145, 146, and 147, a contradiction.Case 3.
Base graph isT113, labeled so that {1,2,3,4} spans a K4 and {5,6,7} spans a K3, with two additional edges (1,5) and (4,5).
The base edgee=67 must generate the triples 167, 267, 367, and 467 and must thus generate an S4. Consider the base edges 23, 56, and 57. 23 must generate the triples 235, 236, and 237; 56 must generate 526, 536; 57 must generate 527 and 537. If 23 generates an S3, then 56, 57 must both generate S4-s, otherwise the triples 147, 146 would be doubly covered. But then there would be three S4-s. Hence 23 generates an S4, and all the remaining edges generate S3-s.
Consider the base edges 12, 13, 14, 24, and 34. Since each of these generates two triples with 6 and 7, their complementaryH3-s contain the triples 345, 245, 235, 135, and 125, respectively. However, the complementary H4 of 67, which w.l.o.g. can be written as either C8(5;1234) or C8(5;1243) must contain at least three of these triples, a contradiction.Case 4.
Base graph isT112, labeled such that {1,2,3,4} spans a K4 and {5,6,7} spans a K3, with two additional edges (4,5), (4,7).
The base edge 56 must generate the triples 156, 256, 356, and the base edge 23 must generate 235, 236, and 237. If both of them generateS3-s, then the complementary H3-s would doubly cover 147. Hence at least one of 56 or 23 must generate an S4. Similarly, if 67, 13 both generate S3-s, then 245 would be doubly covered by their complementary H3-s, and if 57, 12 both generate S3-s, then 346 would be doubly covered. Then we have at least three S4-s, a contradiction.


## 3.1. (10,0,1)

Following the proof of Lemma8, we can label the 10-cycle as C10(12345), and we have 6-cycles on 12467, 13467, 13567, 23567, and 24567. In a 6-cycle, two vertices are repeated in every element. Since the five 6-cycles above contain, respectively, the 3-sets 124, 134, 135, 235, and 245, the two repeated vertices must be from these 3-sets. In particular, the 3-sets 167, 267, 367, 467, and 567 are not contained in any of these 6-cycles. There are ten 4-sets containing these five 3-sets. But each of the five 6-cycles contains one of these 4-sets. Hence there are five remaining 4-sets which contain five 3-sets, and the only possibility is that these ten elements form a 10-cycle. Then there are two 10-cycles, a contradiction.


## 3.2. (1,8,0)

LabelG=T9 so that {1,2,3,4} spans a K4 and {5,6,7} spans a K3.One of the edges of theK3 must generate the triple 567; say e=56. e must also generate the triples 156, 256, 356, and 456. But e can generate at most 4 triples, a contradiction.


## 3.3. (5,5,0)

LabelG=T10 so that {1,2,3,4} spans a K4, {5,6,7} spans a K3, and the tenth edge is (4, 5).(i)
The edgee=67 of G must be the base of a copy P1 of S4 since the triples i,6,7 for i∈[4] must be based on e. Let (w.l.o.g) 1, 2, 3, 4 be the cyclic ordering of the 4-cycle in the copy of H4 complementary to P1 (the triples in C8(5;1234)).(ii)
Consider the four base edges ofG on the 4-cycle U=1,2,3,4,1. We claim that all of them have weight 4. Suppose this is not the case, and f=ij is covered by a star P2 in S3 where i,j are consecutive on U. Observe that the triples i,j,6 and i,j,7 must be in P2. Therefore the triple M={1,2,…,7}∖{i,j,6,7} is covered by the copy of H3 complementary to P2. However, M={5,i+2,j+2} with (mod 4), addition thus it is also covered by the copy of H4 complementary to P1, a contradiction.(iii)
At this point, we know that the five base edges are of weight 4, and the rest of the edges have weight 3. In particular, 13 and 57 have weight 3, and both uniquely determine their stars inS3, namely, 135, 136, 137 and 571, 572, 573. But then the triple 246 is doubly covered by their complementary copies of H3-s, a contradiction, finishing the proof.


## 3.4. (9,2,0)

The base graphT111 cannot occur since the base edge K2 must generate 5 triples.Case 1.
Base graph isT115, the union of edge 12, the triangles 1,3,4 and 2,5,6, and the star 37, 47, 57, 67.
The base edgese=34 and f=56 must generate the triples 234, 345, 346 and 156, 356, 456, respectively. They cannot both generate S3-s because then the triple 127 would be doubly covered by their complementary H3-s.
One ofe, f, say e=34 generates an S4. Suppose first that f generates an S3. Then 13 and 14 both generate S4-s; otherwise 247 or 237 would be doubly covered by their complementary H3-s. But this is a contradiction, having at least three S4-s in the star partition. Thus f also generates an S4. Consequently, 25 and 26 both generate S3-s and their complementary H3-s contain the triples 167 and 157, respectively. However, at least one of these triples is also covered by the complementary H4 of the S4 generated by e, a contradiction.Case 2.
Base graph isT114, labeled so that {1,2,3,4} spans a K4 and {5,6,7} spans a K3, with two additional edges (4,5) (1,7).
The base edgee=23 must generate the triples 235, 236, and 237. Suppose that e generates an S3; then the complementary H3 contains the triples 145, 146, and 147. This implies that the base edges 56, 57, and 67 must all generate S4-s. Otherwise, suppose that 56 generates an S3. Since 56 must generate the triples 256 and 356, the triple 147 is in the complementary H3, and it is doubly covered by the complementary H3 of e. Similarly, if 57 and 67 generate S3-s, then the triples 146 and 145 would be doubly covered. Thus e must generate an S4.
Consider the complementaryH4 generated by e, w.l.o.g. let it be C8(1;4567). Then it contains at least two of the triples 145, 146, and 147, a contradiction.Case 3.
Base graph isT113, labeled so that {1,2,3,4} spans a K4 and {5,6,7} spans a K3, with two additional edges (1,5) and (4,5).
The base edgee=67 must generate the triples 167, 267, 367, and 467 and must thus generate an S4. Consider the base edges 23, 56, and 57. 23 must generate the triples 235, 236, and 237; 56 must generate 526, 536; 57 must generate 527 and 537. If 23 generates an S3, then 56, 57 must both generate S4-s, otherwise the triples 147, 146 would be doubly covered. But then there would be three S4-s. Hence 23 generates an S4, and all the remaining edges generate S3-s.
Consider the base edges 12, 13, 14, 24, and 34. Since each of these generates two triples with 6 and 7, their complementaryH3-s contain the triples 345, 245, 235, 135, and 125, respectively. However, the complementary H4 of 67, which w.l.o.g. can be written as either C8(5;1234) or C8(5;1243) must contain at least three of these triples, a contradiction.Case 4.
Base graph isT112, labeled such that {1,2,3,4} spans a K4 and {5,6,7} spans a K3, with two additional edges (4,5), (4,7).
The base edge 56 must generate the triples 156, 256, 356, and the base edge 23 must generate 235, 236, and 237. If both of them generateS3-s, then the complementary H3-s would doubly cover 147. Hence at least one of 56 or 23 must generate an S4. Similarly, if 67, 13 both generate S3-s, then 245 would be doubly covered by their complementary H3-s, and if 57, 12 both generate S3-s, then 346 would be doubly covered. Then we have at least three S4-s, a contradiction.



---

*Source: 929565-2013-09-12.xml*