1 Erratum to: J Comb Optim (2012) 23:322–330 DOI 10.1007/s10878-010-9299-5

Abstract    The bound on the size of maximum matching given in the paper as follows:

$$\begin{aligned} M \ge \left\{ \begin{array}{l@{\quad }l@{\quad }l} \displaystyle \frac{m}{2}-\frac{m}{2L}, &{} \mathrm{if} &{} k = 2\\ \; &{} \; \\ \displaystyle \frac{m}{k} - \frac{m}{(k+L)k}, &{} \mathrm{if} &{} k > 2 \end{array} \right. \end{aligned}$$

is not accurate. We now correct the bound to

$$\begin{aligned} M \ge \frac{m}{k}-\frac{m}{Lk}, \end{aligned}$$

where \(M\) is the size of the maximum matching in any graph of degree \(k\), \(m\) edges and length of the smallest odd size cycle \(L\).

When no simple odd-length cycle exists it is known previously that \(\displaystyle M \ge \frac{m}{k}\).

We show that the new bound given here is tight.

Keywords   Combinatorial problems \(\cdot \) Graph algorithms \(\cdot \) Matching \(\cdot \) Lower bound

2 Explanation

The bound

$$\begin{aligned} M \ge \left\{ \begin{array}{l@{\quad }l@{\quad }l} \displaystyle \frac{m}{2}-\frac{m}{2L}, &{} \mathrm{if} &{} k = 2\\ \; &{} \; \\ \displaystyle \frac{m}{k} - \frac{m}{(k+L)k}, &{} \mathrm{if} &{} k > 2 \end{array} \right. \end{aligned}$$

given in paper “Tight Bound for Matching” is not accurate, as shown in a complete graph \(G\) of 5 vertices. \(G\) has \(m=10\) edges with degree \(k=4\) and smallest old cycle length \(L=3\) and has maximum matching size 2. By the above formula it should have matching of size \(10/4-10/((4+3)4) > 2.142\). Thus the above formula gives a matching of size 3 that is incorrect. Pim van ‘t Hof found this issue and notified me and he pointed out that the estimate of the number of edges \(n(n-L)/2\) in Case 2 and \(n\ge L+2\) (page 329, line 17) is smaller than the number of edges in the graph and thus resulting in the overestimate of the number of maximum matching edges in the graph.

Now we correct the proof as follows:

We will generalize Case 1 analyzed in the paper to all situations:

There can be no more \(nk/2\) edges in \(C\). Thus we have

$$\begin{aligned} \frac{M}{(n-1)/2} \ge \frac{m}{nk/2} \end{aligned}$$

i.e.:

$$\begin{aligned} M \ge \frac{m}{k}-\frac{m}{nk} \end{aligned}$$

Because \(n\ge L\) we have that:

$$\begin{aligned} M \ge \frac{m}{k}-\frac{m}{Lk} \end{aligned}$$

We now show that this bound is tight.

When \(k=2\), we have any cycle of odd length \(L\) having maximum matching of size \((L-1)/2\). Our bound gives \(L/2-L/(2L)=L/2-1/2=(L-1)/2\).

For graphs of degree \(k\) and smallest odd cycle length \(L\), we create a graph consisting of a cycle of length \(L\) with vertices \(v_0, v_1, \ldots , v_{L-1}\) in the cycle. Then for each even numbered vertex \(v\) we add \(k-2\) edges connecting \(v\) to \(k-2\) degree 1 vertices. In this graph the degree is \(k\), the smallest odd cycle length is \(L\), the number of edges is \((L+1)(k-2)/2+L\). The maximum matching size is \(M=(L+1)/2\). Our bound gives:

$$\begin{aligned} M^\prime&= \frac{(L+1)(k-2)/2+L}{k} - \frac{(L+1)(k-2)/2+L}{Lk}\\&= \frac{L+1}{2}-\frac{1}{k}-\frac{L+1}{2L}+\frac{1}{kL} \end{aligned}$$

Because \(k\ge 3\) and \(L \ge 3\) we have that

$$\begin{aligned} M-1 < \frac{L+1}{2}-1+\frac{1}{kL} \le M^\prime <M. \end{aligned}$$

Thus \(M^\prime \) says that maximum matching size is \(M\) in this case.