1. Introduction
A G-design on H is an edge-disjoint decomposition of H into isomorphic copies of the graph G. When H = Kn, the complete graph on n vertices, this is called a G-design of order n. The spectrum problem for G—determining all n for which such a design exists—has been solved for all graphs on fewer than six vertices [1] [2].
A complete graph with a hole, denoted Kd + v, consists of a complete graph Kd together with an independent set V of v vertices, where every vertex in V is adjacent to every vertex in Kd; see Figure 1. Equivalently, Kd + v = Kn/Kv where n = d + v. Designs with holes were first studied by Doyen and Wilson [3] for G = K3, and extended to cycles and other small graphs [4] [5].
Figure 1. Kd + v.
The graph of primary interest here is K4 − e, the complete graph on four vertices with one edge removed, as shown in Figure 2. Bermond and Schonheim [1] showed a K4 − e design of order n exists if and only if n ≡ 0 or 1 (mod 5) and n ≥ 6. Hoffman, Lindner, Sharry, and Street [6] solved the maximum packing problem for Kn with K4 − e. Reinterpreted, these results settle the Kd + v problem for v ≤ 3.
Figure 2. K4 – e.
In [7], we proved existence for even d when v = 2(d − 1) − 5a for all a ≥ 0, covering all cases where 5 ∤ d. That paper explicitly leaves open the case 5 | d, which is settled here.
Theorem 1.1 (Main Theorem). There exists a K4 − e design on Kd + v when d is even if and only if: (1) 5 | d(d + 2v − 1); (2) v ≤ 2(d − 1); (3) v ≠ 2d − 3 and v ≠ 2d − 4.
Necessity of (1) and (2) follows from standard edge-counting arguments [7]. Condition (3) is established in Section 3. Sufficiency for 5 ∤ d was proven in [7]; this paper provides sufficiency when 5 | d. Section 2 recalls the necessary background. Section 3 establishes non-existence for v = 2d − 3 and 2d − 4. Section 4 gives the recursive and multipartite tools. Section 5 presents the main constructions. Section 6 verifies small base cases. Section 7 proves the main theorem.
2. Preliminaries
Throughout, let W = {(d, v): there exists a K4 − e design on Kd + v}. This is the set of (d, v) pairs for which the existence question has a positive answer; Theorem 1.1 characterizes W restricted to even d. Since d is even, write d = 2t. We model Kd as ℤt × {1, 2} with all possible edges within and between the two copies. Vertices in Kd are called upstairs; vertices in V are called downstairs. There are four types of K4 − e blocks depending on how many vertices lie downstairs, shown in Figure 3.
Figure 3. The four block types α, β, γ, δ.
Concretely: an α block places two vertices upstairs, joined by an edge, with its two downstairs vertices each adjacent to both; a β block places three vertices upstairs, joined by two of the three possible edges, with its single downstairs vertex adjacent to all three; a γ block places three vertices upstairs forming a triangle, with its single downstairs vertex adjacent to two of the three; and a δ block lies entirely upstairs, contributing all five edges of the block within Kd and none between Kd and V. This matches the edge-count equations of Section 2.3 below.
2.1. Pure and Mixed Differences
For integers a and b, define |b − a|t to be the smallest non-negative integer congruent to b − a or a − b (mod t). An edge within a copy of ℤt has pure difference |b − a|t. Pure differences range over {1, …, ⌊t/2⌋}; when t is even the value t/2 is the half difference. An edge between ℤt × {1} and ℤt × {2} has mixed difference y − x (mod t). There are t mixed differences, each forming a 1-factor on the upstairs vertices.
2.2. The Stern-Lenz Lemma
Let Dt = {1, 2, …, ⌊t/2⌋}. Call x ∈ Dt a good difference if t/gcd(x, t) is even.
Lemma 2.1 (Stern and Lenz [8]). G[S] has a 1-factorization if and only if S contains at least one good difference.
The key construction tool is Graph H, shown in Figure 4: take a simple regular graph G and an isomorphic copy G', then add an edge between each vertex and its mate. The resulting H has a 1-factorization. In practice, every time we use a pure difference from ℤt × {1} we use the same difference from ℤt × {2}, ensuring G[S, T, S] has a 1-factorization whenever T ≠ ∅.
Figure 4. Graph H—each vertex is connected to its isomorphic mate, yielding a 1-factorization.
2.3. Block Counts
Counting edges by block type yields two useful equations. Let A, B, Γ, Δ denote the number of blocks of each type:
A + 2B + 3Γ + 5Δ = d(d − 1)/2 (edges upstairs)
4A + 3B + 2Γ = vd (edges between V and Kd)
A base block is developed (mod t) by incrementing upstairs vertex labels to produce t blocks. Each 1-factor of Kd yields t α blocks by pairing with two downstairs vertices.
3. Non-Existence When v = 2d − 3 or v = 2d − 4
The coloring scheme for the non-existence proof is illustrated in Figure 5. Each vertex in V receives a unique color. Upstairs edges are colored according to block type: α-block edges receive two colors, β-block edges one color, the special edge e in a γ block one color, and δ-block edges none.
Figure 5. Colors assigned to upstairs edges by each block type.
Lemma 3.1. When d is even and 5 | d, a K4 − e design on Kd + v does not exist when v = 2d − 3 or v = 2d − 4.
Proof. Let p = upstairs edges with two colors, q = edges with one color (from β or γ), r = pairs of one-colored edges in β blocks, s = uncolored edges. At each upstairs vertex: d − 1 = p + q + 2r + s; the color count gives v = 2p + q + r. The deficiency 2(d − 1) − v = q + 3r + 2s.
Case 1: deficiency = 1. Then q = 1, r = s = 0. The single one-colored edge cannot arise from a γ block (requires s ≥ 1) or a β block (requires r ≥ 1). No other block type produces single one-colored edges. Contradiction; v = 2d − 3 is impossible.
Case 2: deficiency = 2. Either q = 2, r = s = 0, or q = r = 0, s = 1. In either case r = 0 so no β blocks exist. Two one-colored edges must come from γ blocks, but each γ block requires s ≥ 1, and at most one γ block can exist when s ≤ 1. Contradiction; v = 2d − 4 is impossible. □
4. Recursive and Multipartite Constructions
4.1. Blowup Recursion
Lemma 4.1. If (d, v) ∈ W, then (dk, v + 2d(k − 1)) ∈ W for all positive integers k.
Proof. Blow up each upstairs vertex of Kd + v by a factor of k. The k copies of the (d, v) design exhaust all edges incident to V. By Lemma 2.1, the remaining upstairs edges partition into d(k − 1) 1-factors. Pairing each with two new downstairs vertices and forming α blocks yields the desired design. □
4.2. The K10, 10, 10 Design
A complete tripartite graph Ka,b,c has all edges between three parts of sizes a, b, c. Let S = {(a, b, c): there exists a K4 − e design on Ka,b,c}. Figure 6 illustrates how such a multipartite design combines with hole designs to yield a larger design.
Figure 6. Combining Ka,b,c, Kb + v, and Kc + v designs to form Kb+c + (a + v).
Lemma 4.2. (10, 10, 10) ∈ S.
Proof. Label the three parts a, b, c, each with vertex set ℤ10. The following base blocks, developed (mod 10) for 0 ≤ i ≤ 9, partition all edges:
((0 + i, a), (0 + i, b), (2 + i, c), (3 + i, c))
((0 + i, b), (0 + i, c), (2 + i, a), (3 + i, a))
((0 + i, c), (0 + i, a), (2 + i, b), (3 + i, b))
((5 + i, a), (0 + i, b), (1 + i, c), (6 + i, c))
((5 + i, b), (0 + i, c), (1 + i, a), (6 + i, a))
((5 + i, c), (0 + i, a), (1 + i, b), (6 + i, b)) □
Lemma 4.3. If (a, b, c) ∈ S and (b, v), (c, v) ∈ W, then (b + c, a + v) ∈ W.
Proof. The union of blocks from the three component designs on Ka,b,c, Kb + v, and Kc + v partitions the edges of Kb+c + (a + v). □
5. Constructions for 5 | d
Write d = 10t (since 5 | d and d is even). Edges of pure difference t and 2t together with mixed differences 0, t, 2t, 3t, 4t produce t disjoint copies of K10 upstairs. For the upper range of v, these are replaced by K10 + h designs via Lemma 4.1. For the lower range, δ base blocks are constructed using bridges as in [7], and remaining edges are handled via Lemma 2.1. Figure 7 illustrates this construction: the mixed-difference edges of a δ base block form a path alternating between the two upstairs copies, while its two pure-difference edges lie within the rows, so the block can be read directly off the diagram. The same construction, with different endpoints, underlies every δ base block used in Section 6.
Figure 7. The bridge construction: a δ base block read as a path across the two upstairs copies.
5.1. Case: t Odd (t ≥ 3)
Lemma 5.1. Let d = 10t with t odd, t ≥ 3. Then (d, v) ∈ W for all admissible v.
Proof. For 20t − 20 ≤ v ≤ 20t − 2, apply Lemma 4.1 with a (10, h) base design, 0 ≤ h ≤ 18. For smaller v, the following three families of δ base blocks are developed (mod t) for 0 ≤ k ≤ t − 1:
Family 1 (0 ≤ i ≤ t − 2):
((0,1), (2t−1−i, 2), (2t−2−2i, 1), (2t+1+i, 2))
Family 2 (single block):
((0,1), (3t+2, 2), (1, 1), (3t+3, 2))
Family 3 (0 ≤ j ≤ (t−3)/2 − 1):
((0,1), (4t+1+j, 2), (3+2j, 1), (5t−1−j, 2))
This produces t + (t − 3)/2 δ base blocks, covering values v ≥ 5t − 5, which overlaps with the Lemma 4.1 range when t ≥ 3. Cases t = 3 and t = 5 require modifications given in Section 6. □
5.2. Case: t Even (t ≥ 8)
Lemma 5.2. Let d = 10t with t even, t ≥ 8. Then (d, v) ∈ W for all admissible v.
Proof. The upper range is handled by Lemma 4.1. For the lower range, the half difference t is excluded from δ block arcs. The bridge construction skips i = (t − 2)/2 and produces the following three families of modified δ base blocks:
Family 1 (0 ≤ i ≤ t − 2, i ≠ (t−2)/2):
((0,1), (2t−1−i, 2), (2t−2−2i, 1), (2t+1+i, 2))
Family 2 (single block):
((0,1), (3t+2, 2), (1, 1), (3t+3, 2))
Family 3 (0 ≤ j ≤ (t−4)/2 − 1):
((0,1), (4t+2+j, 2), (3+2j, 1), (5t−1−j, 2))
This produces t − 1 + (t − 4)/2 δ base blocks, overlapping with Lemma 4.1 when t ≥ 8. Cases t = 2, 4, 6 are handled in Section 6. □
6. Small Base Cases (d = 10 through 80)
All values v ≤ 3 are resolved by [1] and [6]. We give explicit constructions for each d ∈ {10, 20, 30, 40, 50, 60, 80}. Vertices in V are labeled (0,3), (1,3), … and upstairs vertices belong to ℤt × {1} or ℤt × {2} unless an explicit integer vertex set is given. Every base block and explicit block list in this section was checked computationally to confirm that its development partitions the required edge set exactly once, with no repeated or missing edges; the verification script is available from the author on request. Table 1 summarizes which method covers each v-range for each d.
Table 1. Coverage of Section 6, by d and v-range.
d |
t |
v-range |
Method |
10 |
1 |
v ≤ 3 |
[1], [6] |
10 |
1 |
v = 4, 7, 9 |
[6] |
10 |
1 |
v = 8, 13, 18 |
[7] |
10 |
1 |
v = 5, 6, 10, 11, 12, 14, 15 |
Direct construction, Section 6.1 |
10 |
1 |
v = 16, 17, 19 |
Lemma 4.3 (K10, 10, 10 tripartite) |
20 |
2 |
20 ≤ v ≤ 38 |
Lemma 4.1 (blowup) |
20 |
2 |
v = 18 |
[7], Lemma 3.1 |
20 |
2 |
v = 13 |
[7], Lemma 4.3 |
20 |
2 |
v ∈ {10, 11, 12, 14, 15, 16, 17, 19} |
Lemma 4.3 (tripartite) |
20 |
2 |
v = 9 |
Recursion (Lemma 2.1), x = 8 |
20 |
2 |
4 ≤ v ≤ 8 |
Recursion (Lemma 2.1), x = 10 |
30 |
3 |
20 ≤ v ≤ 58 |
Lemma 5.1, modified δ base blocks |
30 |
3 |
v = 19 |
Recursion, x = 13 |
30 |
3 |
v = 18 |
[7], Lemma 3.1 |
30 |
3 |
v = 16, 17 |
Recursion, x = 14, 12 |
30 |
3 |
11 ≤ v ≤ 15 |
Recursion, x = 10 |
30 |
3 |
v ≤ 10 |
Recursion |
40 |
4 |
20 ≤ v ≤ 78 |
Lemma 5.2, modified δ base blocks |
40 |
4 |
v = 19 |
Recursion, x = 13 |
40 |
4 |
v ≤ 18 |
Recursion |
50 |
5 |
20 ≤ v ≤ 98 |
Lemma 5.1, modified δ base blocks |
50 |
5 |
v ≤ 20 |
Recursion |
60 |
6 |
30 ≤ v ≤ 118 |
Lemma 5.2 + one extra δ base block |
60 |
6 |
v < 30 |
Recursion |
80 |
8 |
50 ≤ v ≤ 158 |
Lemma 5.2 (applies directly) |
80 |
8 |
v = 48, 49 |
Recursion, x = 30 |
80 |
8 |
v ≤ 47 |
Recursion |
t odd, t ≥ 3 (general) |
— |
all admissible v |
Lemma 5.1 (Section 5.1) |
t even, t ≥ 8 (general) |
— |
all admissible v |
Lemma 5.2 (Section 5.2) |
6.1. d = 10 (t = 1)
Previously solved: v = 1, 2, 3 [6]; v = 4, 7, 9 [6]; v = 8, 13, 18 [7].
v = 4. Let {1, 2, …, 10} be the vertices upstairs:
(5,6,(2,3),(3,3)), (4,10,(2,3),(3,3)), (3,9,(2,3),(3,3)), (2,8,(2,3),(3,3)),
(1,7,(2,3),(3,3)), ((1,3),3,1,7), (1,4,2,8), (2,5,3,9),
(3,(0,3),4,10), (4,7,5,6), (5,8,(0,3),(1,3)), ((0,3),9,7,1),
(7,10,8,2), (8,6,9,3), (9,(1,3),10,4), (10,1,6,5), (6,2,(1,3),(0,3)).
v = 5. Let {0, 1, …, 9} be the vertices upstairs:
((1,3),1,0,2), (9,3,(1,3),1), ((1,3),6,5,7), (8,3,(1,3),6),
(7,1,5,8), (7,2,3,4), (6,2,0,3), (3,4,5,0), (8,9,5,0),
(1,4,(2,3),(3,3)), (6,9,(2,3),(3,3)), (6,1,(0,3),(4,3)), (0,4,(0,3),(4,3)),
(5,2,(2,3),(3,3)), (8,3,(2,3),(3,3)), (7,0,(2,3),(3,3)),
(5,0,(0,3),(4,3)), (7,3,(0,3),(4,3)), (8,2,(0,3),(4,3)).
v = 6. ℤ5 × {1} ∪ {(0,3)} and ℤ5 × {2} ∪ {(0,3)} each form K6 decomposed into 6 blocks. Remaining blocks:
((1,3),(0,1),(0,2),(1,2)), ((2,3),(1,1),(1,2),(2,2)),
((3,3),(2,1),(2,2),(3,2)), ((4,3),(3,1),(3,2),(4,2)),
((5,3),(4,1),(4,2),(0,2)), ((1,3),(2,2),(4,1),(3,1)),
((2,3),(3,2),(0,1),(4,1)), ((3,3),(4,2),(1,1),(0,1)),
((4,3),(0,2),(2,1),(1,1)), ((5,3),(1,2),(3,1),(2,1)),
((0,1),(2,2),(4,3),(5,3)), ((1,1),(3,2),(1,3),(5,3)),
((2,1),(4,2),(1,3),(2,3)), ((3,1),(0,2),(2,3),(3,3)), ((4,1),(1,2),(3,3),(4,3)).
v = 7. Let {1, 2, …, 10} be the vertices upstairs:
((0,3),7,5,8), ((0,3),10,6,9), (1,2,(0,3),(4,3)), (3,4,(0,3),(1,3)),
((1,3),1,7,9), ((1,3),2,10,8), (6,5,(1,3),(2,3)),
((2,3),8,1,3), ((2,3),9,2,4), (7,10,(2,3),(3,3)),
((3,3),4,1,5), ((3,3),3,2,6), (8,9,(3,3),(4,3)),
((4,3),5,3,10), ((4,3),6,4,7), ((5,3),5,1,8), (3,10,(5,3),1),
((5,3),6,2,9), (4,7,(5,3),2), ((6,3),5,2,9), (3,7,(6,3),9),
((6,3),6,1,8), (4,10,(6,3),8).
v = 9. Let {1, 2, …, 10} be the vertices upstairs:
((0,3),1,4,10), ((0,3),7,2,3), (5,8,(0,3),(2,3)), (6,9,(0,3),(1,3)),
((1,3),1,2,8), ((1,3),5,3,4), (7,10,(1,3),(2,3)),
((2,3),1,3,9), ((2,3),6,2,4),
(1,5,(3,3),(4,3)), (2,8,(3,3),(4,3)), (3,4,(3,3),(4,3)),
(6,7,(3,3),(4,3)), (9,10,(3,3),(4,3)),
(1,6,(5,3),(6,3)), (2,4,(5,3),(6,3)), (3,9,(5,3),(6,3)),
(5,7,(5,3),(6,3)), (8,10,(5,3),(6,3)),
(1,7,(7,3),(8,3)), (2,3,(7,3),(8,3)), (4,10,(7,3),(8,3)),
(8,9,(7,3),(8,3)), (2,5,9,10), (3,6,8,10), (4,7,8,9).
v = 10. Let {0, 1, …, 9} be the vertices upstairs:
((i,3), i, 8, 9) for 0 ≤ i ≤ 7,
((0,3),7,2,1), ((6,3),5,0,7), ((7,3),6,1,0),
(0,1,(4,3),(6,3)), (1,2,(5,3),(7,3)), (2,2,(0,3),(6,3)),
(3,4,(1,3),(7,3)), (4,5,(0,3),(2,3)), (5,6,(1,3),(3,3)),
(6,7,(2,3),(4,3)), (7,0,(5,3),(3,3)),
(8,9,(8,3),(9,3)), (0,4,(8,3),(9,3)), (1,5,(8,3),(9,3)),
(2,6,(8,3),(9,3)), (3,7,(8,3),(9,3)).
v = 11. Put a (5,1) design on ℤ5 × {1} ∪ {(0,3)} and ℤ5 × {2} ∪ {(0,3)}. Use mixed differences 0 through 4 for α blocks with the remaining 10 vertices in V.
v = 12. Let {1, 2, …, 10} be the vertices upstairs:
((i,3), i, 7, 8) for 1≤i≤6, ((j+1,3), j, 9, 10) for 1≤j≤5, ((1,3),6,9,10),
(1,6,(3,3),(4,3)), (1,2,(5,3),(6,3)), (3,6,(2,3),(3,3)), (3,4,(1,3),(6,3)),
(1,5,(7,3),(8,3)), (4,6,(7,3),(8,3)), (2,3,(7,3),(8,3)), (7,8,(7,3),(8,3)),
(9,10,(7,3),(8,3)), (1,3,(11,3),(12,3)), (2,4,(11,3),(12,3)), (5,6,(11,3),(12,3)),
(7,9,(11,3),(12,3)), (8,10,(11,3),(12,3)), (1,4,(9,3),(10,3)), (2,6,(9,3),(10,3)),
(3,5,(9,3),(10,3)), (8,9,(9,3),(10,3)), (7,10,(9,3),(10,3)).
v = 14.
((1,3),(0,1),(4,1),(1,1)), ((1,3),(0,2),(4,2),(1,2)),
((2,3),(1,1),(4,1),(2,1)), ((2,3),(1,2),(4,2),(2,2)),
((3,3),(2,1),(4,1),(3,1)), ((3,3),(2,2),(4,2),(3,2)),
((4,3),(3,1),(4,1),(0,2)), ((4,3),(3,3),(4,2),(0,1)),
((3,1),(3,2),(1,3),(2,3)), ((2,1),(2,2),(1,3),(4,3)), ((1,1),(1,2),(3,3),(4,3)),
((0,1),(0,2),(2,3),(3,3)), ((3,1),(4,2),(5,3),(6,3)), ((2,1),(0,1),(4,3),(6,3)),
((0,1),(0,2),(5,3),(6,3)), ((4,1),(2,2),(5,3),(6,3)), ((3,2),(1,2),(5,3),(6,3)),
((3,1),(2,2),(7,3),(8,3)), ((2,1),(0,2),(7,3),(8,3)), ((1,1),(3,2),(7,3),(8,3)),
((0,1),(1,2),(7,3),(8,3)), ((4,2),(4,1),(7,3),(8,3)),
((3,1),(0,1),(9,3),(10,3)), ((2,1),(4,2),(9,3),(10,3)),
((1,1),(2,2),(9,3),(10,3)), ((4,1),(1,2),(9,3),(10,3)),
((3,2),(1,2),(0,3),(10,3)), ((3,1),(1,2),(11,3),(12,3)),
((2,1),(3,2),(11,3),(12,3)), ((1,4),(4,2),(11,3),(12,3)),
((0,1),(2,2),(11,3),(12,3)), ((4,1),(0,2),(11,3),(12,3)),
((3,1),(1,1),(13,3),(14,3)), ((0,1),(4,2),(13,3),(14,3)),
((4,1),(3,2),(13,3),(14,3)), ((2,2),(0,2),(13,3),(14,3)),
((2,1),(1,2),(13,3),(14,3)).
v = 15.
((1,3),(4,1),(0,1),(1,1)), ((1,3),(4,1),(0,2),(1,1)),
((2,3),(3,1),(0,1),(1,1)), ((2,3),(3,2),(0,2),(1,2)),
((3,3),(2,1),(0,1),(1,1)), ((3,3),(2,2),(0,2),(1,2)),
((0,1),(0,2),(6,3),(7,3)), ((1,1),(1,2),(6,3),(7,3)),
((2,1),(2,2),(4,3),(7,3)), ((3,1),(3,2),(6,3),(7,3)), ((4,1),(4,2),(5,3),(7,3)),
((3,1),(2,1),(1,3),(5,3)), ((3,2),(2,2),(1,3),(5,3)),
((4,1),(2,1),(2,3),(6,3)), ((4,2),(2,2),(2,3),(6,3)),
((3,1),(4,1),(3,3),(4,3)), ((3,2),(4,2),(3,3),(4,3)),
((0,1),(1,1),(4,3),(5,3)), ((0,2),(1,2),(4,3),(5,3)).
Use mixed differences 1, 2, 3, and 4 for α blocks with vertices 8 through 15 in V.
The remaining admissible values v ∈ {16, 17, 19} follow from Lemma 4.3 with (a, b, c) = (10, 10, 10) and v = 6, 7, 9 in the component designs.
6.2. d = 20 (t = 2)
For 20 ≤ v ≤ 38: Lemma 4.1 with (10, h), 0 ≤ h ≤ 18. v = 18: Lemma 3.1 of [7]. v = 13: Lemma 4.3 of [7].
v ∈ {10, 11, 12, 14, 15, 16, 17, 19}: Lemma 4.3 with (a,b,c) = (10, 10, 10) and v = 0, 1, 2, 4, 5, 6, 7, 9 in components.
v = 9: Recursion with x = 8. 4 ≤ v ≤ 8: Recursion with x = 10.
6.3. d = 30 (t = 3)
For 20 ≤ v ≤ 58: Lemma 5.1 with δ base blocks:
((0,1),(4,2),(2,1),(8,2)), ((0,1),(5,2),(4,1),(7,2)).
v = 19: Recursion x = 13. v = 18: [7] Lemma 3.1. v = 16, 17: Recursion x = 14, 12. 11 ≤ v ≤ 15: Recursion x = 10. v ≤ 10: Recursion applies.
6.4. d = 40 (t = 4)
For 20 ≤ v ≤ 78: Lemma 5.2 with δ base blocks:
((0,1),(2,2),(1,1),(3,2)), ((0,1),(0,2),(3,1),(14,2)),
((0,1),(10,2),(5,1),(13,2)), ((0,1),(17,2),(2,1),(19,2)).
v = 19: Recursion x = 13. v ≤ 18: Recursion applies.
6.5. d = 50 (t = 5)
For 20 ≤ v ≤ 98: Lemma 5.1 with δ base blocks:
((0,1),(6,2),(2,1),(14,2)), ((0,1),(7,2),(4,1),(13,2)),
((0,1),(8,2),(6,1),(12,2)), ((0,1),(9,2),(8,1),(11,2)),
((0,1),(18,2),(1,1),(21,2)), ((0,1),(22,2),(3,1),(23,2)).
v ≤ 20: Recursion applies.
6.6. d = 60 (t = 6)
For 30 ≤ v ≤ 118: Lemma 5.2 with δ base blocks from Case 3 plus:
((0,1),(15,2),(12,1),(27,2)).
v < 30: Recursion applies.
6.7. d = 80 (t = 8)
For 50 ≤ v ≤ 158: Lemma 5.2 applies directly.
v = 49, 48: Recursion x = 30. v ≤ 47: Recursion applies.
7. Proof of the Main Theorem
Proof. Necessity: Condition (1) follows from divisibility of edges by 5; condition (2) from v ≤ 2(d − 1); condition (3) from Lemma 3.1.
Sufficiency: Suppose d is even and conditions (1)-(3) hold. Write d = 10t. The case 5 ∤ d is handled by [7]. When 5 | d: if t is odd and ≥ 3, Lemma 5.1 applies; if t is even and ≥ 8, Lemma 5.2 applies; if t ∈ {1, 2, 3, 4, 5, 6, 8}, Section 6 supplies explicit constructions. In each case a valid K4 − e design on Kd + v is produced.
□
8. Conclusions
We have completed the existence theory for K4 − e designs on Kd + v in the case 5 | d, d even. Combined with [7], the full spectrum problem for even d is now settled by the conditions of Theorem 1.1.
The case d odd remains open. When d is odd, 1-factors do not exist upstairs and the difference-method constructions used here do not apply. However, the recursion (Lemma 2.1) and Lemma 4.3 hold regardless of parity and may prove useful. The known counterexample K5 + 2 shows conditions (1)-(2) are insufficient for odd d, and a complete characterization remains an open problem.