Proof. We assume that (j, j) is a loop in D(A). As δkmax (A) = 0, there exist
PND cycles in D(A) σ1, σ2, . . . , σt in D(A) covering kmax nodes. We need to
show there exist PND cycles σ10 , σ20 , . . . , σt00 in D(A), at least one being a loop,
that cover kmax or kmax - 1 nodes.
Clearly if (j, j) ∈ {σ1, σ2, . . . , σt} then we can use Theorem 6 and we are
done, so assume not. Then j is covered by these cycles, as otherwise, (j, j)
together with σ1 , σ2 , . . . , σt would form PND cycles in D(A) covering kmax + 1
nodes, which contradicts the definition of kmax . Hence there exists one cycle
σr = (j, i2, i3, . . . , ip, j) ∈ {σ1, σ2, . . . , σt}.
If p is odd, then we can split σr - j , and add (j, j ) to the resulting cycles
to form PND cycles in D(A) covering kmax nodes. If instead p is even, then we
can split σr , remove the 2-cycle that contains p, and add (j, j) to the remaining
cycles to form PND cycles in D(A) covering kmax - 1 nodes. The result then
follows from Theorem 6. □
For A ∈ Rn×n, we define F = {k ∈ N; δk(A) = -∞}. By Corollary 4, for
symmetric matrices, unless kmax = 1, the smallest even k ∈ F is 2. However,
the smallest odd value in F is more tricky. We denote this value by koddmin .
Remark. If there exist PND cycles σ1, σ2, . . . , σt in D(A) such that an odd
number of nodes is covered, then at least one of the cycles is odd. Hence
koddmin is the length of a shortest odd cycle in D(A). This cycle can be found
polynomially [19]. Note that koddmin does not exist if there is no odd cycle in
D(A), and if this is the case, then δk = -∞ for all odd k. For the remainder of
this section, we shall assume that koddmin exists.
Theorem 8. Let A ∈ Tn×n be a symmetric matrix, σ1 , σ2, . . . , σt be a collection
of PND cycles in D(A) covering k0 nodes, with at least one having odd length.
Then δk (A) = 0 for all odd k ∈ {l0, . . . , k0}, where l0 is the minimum length of
the odd cycles in this collection.
Proof. Without loss of generality, assume the length of σt is l0 . Then the PND
cycles σ1, σ2, . . . , σt-1 in D(A) cover k0-l0 nodes, hence δk0 -l0 = 0. By Corollary
4, δk = 0 for all even k ∈ {0, . . . , k0 - l0}. Take an arbitrary even k ∈ {0, . . . , k0 -
l0}. So k + l0 ∈ {l0, . . . , k0}. There exist PND cycles σ10 , σ20 , . . . , σt00 in D(A)
covering k nodes other than those in V (σt). Therefore, σ10 , σ20 , . . . , σt00 and σt
are PND cycles in D(A) covering k + l0 nodes. Hence the result. □