New Results on Graph Matching from Degree-Preserving Growth

Abstract

The recently introduced model in S. R. Kharel et al.’s study [Degree-preserving network growth. Nature Physics 2022, 18, 100–106] uses matchings to insert new vertices of prescribed degrees into the current graph of an ever-growing graph sequence. The process depends both on the size of the largest available matching, which is the focus of this paper, as well as on the actual choice of the matching. Here, we first show that the question of whether a graphic degree sequence, extended with a new degree $2\delta$, remains graphic is equivalent to the existence of a realization of the original degree sequence with a matching of size $\delta$. Secondly, we present lower bounds for the size of the maximum matchings in any realization of the degree sequence. We then study the bounds on the size of maximal matchings in some realizations of the sequence, known as the potential matching number. We also estimate the minimum size of both maximal and maximum matchings, as determined by the degree sequence, independently of graphical realizations. Along this line we answer a question raised by T. Biedl et al.: Tight bounds on maximal and maximum matchings. Discrete Mathematics 2004, 285, 7–15.

1. Introduction

The recently introduced degree-preserving growth (DPG) network evolution dynamics (see [1,2]) chooses k pairwise independent edges (a k-matching, where k may be chosen dynamically), deletes those edges, and connects all the end points of the original edges with a new vertex v. This operation is also called the pinching of edges by the incoming vertex v. The degree of the new vertex is $d\left(v\right)=2k$, and the process keeps the degrees of all the original vertices unchanged, which is the reason for the name degree-preserving network growth (DPG). This mechanism is in sharp contrast with previous network growth dynamic models (such as the preferential attachment model, or the Chung-Lu model for generating scale-free networks) where some of the existing nodes must increase their degrees whenever a new node attaches to them. (Note, the incoming node’s degree can also be odd [2], but we will not consider that here.)

Clearly, the process depends on the degree k of the incoming vertex, and also on the actual choice of the matchings to be used. For example, the chosen matching may always have the same size, thus generating a regular graph sequence, or the chosen matchings can always be maximum ones, providing center–periphery-like networks (see [1]). The choice of the matching of a given size can also vary (as there can be several matchings of a given size, in general). Clearly, different strategies for these choices provide different network evolution dynamics. The DPG mechanism defines a whole family of network growth models, proving useful in network modeling applications [1]. For example, it was proved that it can simulate the outputs of several, previously known network growth dynamics, including scale-free networks, and furthermore, it can generate most real-world networks precisely, i.e., the exact graph, edge-by-edge [1]. Interestingly, the latter, numerically observed property is in contrast with the fact (proven in [2]), that DPG construction is NP-hard, in general. Finally, we mention that the DPG process has an interesting application in number theory and to prime gaps, in particular [3].

In this paper, we focus on the study of the available matchings in the different realizations of a given degree sequence. The largest size of a matching in finite graphs is called the graph’s matching number, denoted by $\nu \left(G\right)$, and it is a graph invariant. It is well-known that there exist polynomial-time algorithms that find a maximum size matching in any given simple graph G (for example, the “blossom” algorithm of Edmonds [4]). However, it is difficult to estimate the matching number analytically on the basis of several commonly used graph parameters. For example, two graphs with the same degree sequence may have very different matching numbers (consider the disjoint union of $2k$ triangles and of the cycle $C_{6k}$ of length $6k$, i.e., $\nu =2k$ vs. $\nu =3k$), even by orders of magnitude (see Section 4). Furthermore, local operations (such as manipulating one vertex and its neighbors) on the graph may change this number significantly. For example, in the friendship graph $F_k$ (which is formed by k copies of $K_3$, overlapping in one vertex), the matching number is $\nu \left(F_k\right)=k$. However, after one DPG step [1] (using the edges of the maximum matching) we obtain the complete bipartite graph $K_{2,2k}$ with $\nu \left(K_{2,2k}\right)=2$.

The goal of this paper is twofold. First, it aims to study the maximal possible matching number among all the possible graphical realizations of a degree sequence (potential matching number), see Section 2. Second, (in Section 3), it aims to study the size of maximal matchings of arbitrary graphs with given degree sequences (forcible matching number). These quantities may help to design new graph growth dynamics to achieve networks with predefined structural properties. We will also answer a question, first raised by Biedl, Demaine et al. in [5] (see Theorem 8). Section 3.2 further improves on some of the results in Section 3.

The topic of potentially or forcibly P-graphic properties is widely studied, but as far as we are aware, not in the context of matchings. For an early survey paper about the general notions see Rao, [6]. These notions had most likely been inspired by the work of C. Nash-Williams, who introduced the terms of potentially Hamiltonian and forcibly Hamiltonian, already in 1969 (see [7]). However, this article has not been surveyed in [6].

Next, we fix the exact notion of a matching as it will be applied in this paper. Let G be a simple graph. Consider a non-negative integer-valued function $f\left(v\right)$, defined on $V\left(G\right)$. The subgraph $F\subseteq G$ is an f-factor if ${deg}_F\left(v\right)=f\left(v\right)$ for all $v\in V\left(G\right)$. For vertices with $f\left(v\right)=0$, the vertex does not belong to F. A 1-factor is a spanning subgraph with all degree-one vertices and thus it forms a perfect matching in G. When the f-values vary between 0 and 1, then the f-factor is a (partial) matching or a $(0,1)$-factor. For simplicity, we will use the slightly ambiguous notion of $\delta$-matching for $(0,1)$-factors of $2\delta$ ones in f.

For a given graph G, the existence of a 1-factor is fully determined by Tutte’s 1-Factor theorem (see [8]). Deciding whether there exists an f-factor in G, in general, is also relatively easy: the problem is equivalent to finding a 1-factor in a graph derived from G using Tutte-gadgets (see [8]).

However, the potentially and forcibly f-factor problems in general are not well understood. The forcibly 1-factor graphic problem has been solved for a long time, see Bondy and Chvátal, [9]. Furthermore, J. Petersen proved in 1891 [10] that every even-degree regular graph contains a 2-factor, and thus such degree sequences are forcibly 2-factor graphic. In 2012, Bauer, Broersma, van den Heuvel, Kahl, and Schmeichel [11] proved a necessary and sufficient condition for degree sequences to be forcibly 2-factor graphic, but the conditions are very complex. In this paper, we provide novel results on both the potentially and forcibly $(0,1)$-factor problems.

2. Potentially (0,1)-Factor Graphical Degree Sequences

A sequence $\mathbf{d}$ of n positive integers (n-sequence) is graphic, if there is a graph with a vertex labeling, such that the degree sequence of the graph is $\mathbf{d}$. Such a graph is called a realization of the graphic sequence $\mathbf{d}$. Let us recall an algorithmic characterization of graphic sequences, introduced independently by Havel and Hakimi:

Theorem 1

(Havel, 1955 [12] and Hakimi, 1962 [13]). There exists a simple graph with degree sequence $d_1>0$, $d_2\ge \dots \ge d_n\ge 0$ if and only if the degree sequence ${\mathbf{d}}^{\prime }=d_2-1,\dots ,d_{d_1+1}-1,d_{d_1+2},\dots ,d_n$ is graphic.

Theorem 1 also provides the simple quadratic HH algorithm to generate an actual graph with the given degree sequence (if there is any). At the same time it is interesting to remark that the HH algorithm cannot construct all realizations of a graphic sequence (see, for example ([14], Figure 1)). To be able to do so, further considerations are necessary, such as the star-constrained graphicality theorem-based algorithm ([14], Theorem 6).

2.1. Extended Degree Sequences and Matchings

Next, we study the conditions under which we can extend a graphic degree sequence with an even degree. Let us consider a non-increasing graphic sequence $\mathbf{d}$ and an integer $\Delta >0$. We want to find necessary and sufficient conditions to ensure that the extended degree sequence $\mathbf{d}\circ \Delta =d_1,\dots ,d_n,\Delta$ is graphic. (By the handshake lemma, $\Delta$ should be even.) It is also clear that Theorem 1 provides the following statement.

Lemma 1.

Given a non-increasing graphic sequence $\mathbf{d}$ and a positive integer $\delta \le n/2$, the extended sequence $\mathbf{D}\left(2\delta \right)=\mathbf{d}\circ \left(2\delta \right)$ is graphic if and only if the sequence ${\mathbf{d}}^{\prime }:=d_1-1,\dots ,$$d_{2\delta }-1,d_{2\delta +1},\dots ,d_n$ is also graphic.

Next, we show that the graphicality of the extended sequence is closely related to the existence of large enough matchings in some realizations of the graphic sequence. To prove that, we introduce several notions and notations.

The number of edges in G is denoted by $m\left(G\right)=\left|E\right(G\left)\right|$ and the maximum degree in G by $\Delta \left(G\right)$. When G is known from the context, we use only m or $\Delta$. The degree sequence of a graph G is denoted by $\mathbf{d}\left(G\right)$, while the degree of a vertex v in a degree sequence $\mathbf{d}=\mathbf{d}\left(G\right)$ is denoted by $d\left(v\right)$. The i^th element of a degree sequence $\mathbf{d}$ is denoted by $d_i$.

A matching is a set of pairwise independent edges, and a k-matching is a matching comprising k edges. A matching is maximum if it has the greatest cardinality among all matchings in G. We will use the notation $\nu \left(G\right)$ for this maximum cardinality matching (recall, this is the matching number of G). In turn, a matching is maximal if it is not a proper subset of another matching. Clearly, all maximum matchings are maximal, but not vice versa. Let M be a matching in some graph G. As usual, we say that a vertex $v\in V\left(G\right)$ is matched if there exists an edge in M incident with v.

Consider the integer sequence $\mathbf{k}=(k_1,k_2,\dots ,k_n)$, where for all i we have $k-1\le k_i\le k$ where k is a natural number. The following, lesser-known theorem was conjectured by Grünbaum, [15] (Generalized k-factor Conjecture), and was first proven in [16]:

Theorem 2

(Kundu, 1973). Let $\mathbf{d}=(d_1,d_2,\dots ,d_n)$ and $(d_1-k_1,d_2-k_2,\dots ,d_n-k_n)$ be two graphic sequences. Then, there exists a realization of $\mathbf{d}$ which contains a $\mathbf{k}$-factor.

In the language introduced earlier, it gives a condition for a degree sequence for being potentially k-factor graphic. In the following we will consider only $(0,1)$-factors. In 1974, Lovász, independently from [16], gave a simple proof for the case $\mathbf{k}=(1,\dots ,1)$ [17].

As far as we know, the following application of Kundu’s theorem is new.

Theorem 3

(Weak extension condition). Given a graphic sequence $\mathbf{d}$ and a positive integer $\delta \le n/2$, the sequence $\mathbf{D}\left(2\delta \right)=\mathbf{d}\circ \left(2\delta \right)$ is graphic if and only if the sequence $\mathbf{d}$ has a realization with a matching of size δ.

We remark that while technically the proof is quite simple, the statement itself is rather surprising, and in the context of the DPG processes it is especially meaningful.

Proof. 

If a realization G of the graphic sequence $\mathbf{d}$ has a matching M of size $\delta$, then we construct $G^{+}$ by pinching the edges of the matching M onto a new vertex v: let $V\left(G^{+}\right)=V\left(G\right)\cup \left\{v\right\}$, and let

$$E\left(G^{+}\right)=E\left(G\right)-M+\left\{vu\right|u\in \cup M\}.$$

It is easy to see that the degree sequence of $G^{+}$ is $\mathbf{d}\circ \left(2\delta \right)$.

For the other direction, let $G^{+}$ be a realization of $\mathbf{d}\circ \left(2\delta \right)$ on the vertex set $V^{+}$ and let $v\in V^{+}$ be a vertex with degree $d\left(v\right)=2\delta$. Take the subgraph $G=G^{+}-v$ (delete the vertex v and its incident edges). Since both $\mathbf{d}$ and $d\left(G\right)$ are graphic degree sequences on the vertex set $(V^{+}-v)$, and $\mathbf{d}=d\left(G\right)+\mathbf{k}$ where $\mathbf{k}$ has $2\delta$ ones and $n-2\delta$ zeros, Kundu’s theorem immediately implies that there is a realization of $\mathbf{d}$ on $(V^{+}-v)$ which contains a $\delta$-matching on the neighbors of v in $G^{+}$. □

Let us recall the following well-known fact:

Lemma 2.

Let $\mathbf{d}$ be a non-increasing positive integer sequence, and let $\mathbf{d}\circ \left(2\delta \right)$ be graphic. Let G be a realization of $\mathbf{d}\circ \left(2\delta \right)$, where $deg\left(u\right)=2\delta$. If $u{v}_i\in E\left(G\right)$ and $u{v}_j\notin E\left(G\right)$ for some $j<i$, then there exists another realization $G^{\prime }$ of $\mathbf{d}\circ \left(2\delta \right)$ where $u{v}_j\in E\left(G^{\prime }\right)$ and $u{v}_i\notin E\left(G^{\prime }\right)$, but the rest of the neighborhood of u is not changed.

This statement motivates introducing a partial ordering on all $(0,1)$ sequence $\mathbf{k}$ with $2\delta$ ones:

$(\ast )$

${\mathbf{k}}_1⪯{\mathbf{k}}_2$ if and only if the ones in ${\mathbf{k}}_1$ can be produced from the ones in ${\mathbf{k}}_2$ by left-shifting.

Lemma 3.

Let $\mathbf{d}$ be a non-increasing positive integer n-sequence, and let $\mathbf{k}$ be a $(0,1)$ sequence with $2\delta$ ones. If sequence $\mathbf{d}-\mathbf{k}$ is graphic, then so is the sequence $\mathbf{d}-{\mathbf{k}}^{\prime }$, for all ${\mathbf{k}}^{\prime }$ where ${\mathbf{k}}^{\prime }⪯\mathbf{k}$.

Note, we do not assume that $\mathbf{d}$ is graphic.

Proof. 

Let G be a realization of the graphic sequence $\mathbf{d}-\mathbf{k}($. We construct a new graph $G^{\prime }$ by adding a new vertex u to G and connecting it to each $v_i$ where $\mathbf{k}\left(i\right)=1$. The degree sequence of $G^{\prime }$ is $\mathbf{D}\left(2\delta \right)=\mathbf{d}\circ \left(2\delta \right)$.

Next, we (iteratively) apply Lemma 2 to $G^{\prime }$. Therefore, since ${\mathbf{k}}^{\prime }⪯\mathbf{k}$,

(∗∗)

there exists another graphic realization $G^{\ast }$ of $\mathbf{D}\left(2\delta \right)$ where the neighbors of u are those $v_i$, for which ${\mathbf{k}}^{\prime }\left(i\right)$ are ones.

We remark that statement $(\ast \ast )$ is similar to ([14] Lemma 4). Now deleting u and its edges from $G^{\ast }$, we obtain a graph $G^{+}$ whose degree sequence is $\mathbf{d}-{\mathbf{k}}^{\prime }$. □

Corollary 1.

Let $\mathbf{d}$ be a non-increasing graphic degree sequence. The degree sequence $\mathbf{d}$ has a realization with a matching of size δ if and only if the sequence $d_1-1,\dots ,d_{2\delta }-1,d_{2\delta +1},\dots ,d_n$ is graphic.

Proof. 

(⇒) Assume there is a realization G of $\mathbf{d}$ which contains a $\delta$-matching. Delete this matching, obtaining a graph with degree sequence $\mathbf{d}-\mathbf{k}$ where $\mathbf{k}$ has $2\delta$ ones. Since ${\mathbf{k}}_0$ with ones on the first $2\delta$ positions is the minimal element in the poset, Lemma 3 proves the statement.

(⇐) Since, by assumption, $\mathbf{d}-{\mathbf{k}}_0$ is graphic, Kundu’s Theorem 2 provides a realization with a $\delta$-matching. □

Now, Lemma 1 and Corollary 1 lead immediately to a strengthening of Theorem 3:

Theorem 4

(Strong extension condition). Given a graphic sequence $\mathbf{d}$ and a positive even integer $\delta \le n/2$, the sequence $\mathbf{D}\left(2\delta \right)=\mathbf{d}\circ \left(2\delta \right)$ is graphic if and only if the sequence $\mathbf{d}$ has a realization with a matching of size δ that covers the vertices with the largest $2\delta$ degrees.

The special case of this result for perfect matchings was proven by Lovász and Plummer in ([18] [Theorem 10.3.3]). The proof of Corollary 1 from Theorem 3 is not difficult. However, one can argue that this statement can play a similar role as the (also simple) Havel–Hakimi theorem.

Corollary 2.

Let $\mathbf{d}$ be a non-increasing graphic sequence on n vertices. If the sequence $\mathbf{D}\left(2\delta \right)=\mathbf{d}\circ \left(2\delta \right)$ is graphic, then the sequence $\mathbf{D}\left(2{\delta }^{\prime }\right)$ is also graphic for all positive integers ${\delta }^{\prime }$ less than δ.

Proof. 

Since sequence $\mathbf{D}\left(2\delta \right)$ is graphic, by Theorem 4, the graphic sequence $\mathbf{d}$ has a graphic realization with $\delta$ independent edges, and thus it also has ${\delta }^{\prime }$ independent edges. The graphicality of $\mathbf{D}\left(2{\delta }^{\prime }\right)$ follows from Theorem 4. □

In view of Corollary 2, one can easily find the largest integer ${\delta }^{\ast }$ for which $\mathbf{D}\left(2{\delta }^{\ast }\right)$ is graphic, by running a binary search on the interval $\delta \in [2,\lfloor n/2\rfloor ]$.

2.2. Potentially Maximum Matchings—Analytically

In this subsection, we derive the exact size (Theorem 6) and a lower bound (Theorem 7) of the potentially maximum matching of a given degree sequence from the Erdős–Gallai inequalities.

Definition 1.

Denote by $\mathcal{G}\left(\mathbf{d}\right)$ the set of all labeled simple graph realizations of a graphic degree sequence $\mathbf{d}$ and let

$${\nu }^{\ast }\left(\mathbf{d}\right)=\underset{G\in \mathcal{G}\left(\mathbf{d}\right)}{max}\nu \left(G\right)$$

(1)

denote the largest matching number among all of its realizations. (Of course ${\nu }^{\ast }={\delta }^{\ast }$, where the latter was determined at end of the previous subsection.)

Here, we are looking for an analytical formula for ${\nu }^{\ast }$ involving as few inequalities as possible. The basis of our study is the well-known Erdős–Gallai theorem:

Theorem 5

(Erdős–Gallai, 1961, [19]). A non-increasing degree sequence $\mathbf{d}$ on n vertices is graphic if and only if ${\sum }_{i=1}^n{d}_i$ is even and

$$\sum _{i=1}^k{d}_i\le k(k-1)+\sum _{i=k+1}^{n}min\{d_i,k\}$$

(2)

holds for any $1\le k\le n$. The equivalence is true even if (2) is required to hold only for $k=n$ and those k that satisfy $d_k>d_{k+1}$.

This theorem can be also derived from Tutte’s factor theorem (see [20]). Theorem 3 implies that ${\nu }^{\ast }\left(\mathbf{d}\right)$ can be determined in polynomial time by finding the largest integer $\delta$ for which $\mathbf{d}\circ \left(2\delta \right)$ is graphical, which can easily be checked via the Erdős–Gallai inequalities. However, a number of these inequalities need not be checked in this scenario, as we will prove in Theorem 6.

Definition 2.

For any non-increasing degree sequence $\mathbf{d}$, let

$$t_{\mathbf{d}}\left(\delta \right)=\left|\left\{i>\delta |d_i=d_{\delta }\right\}\right|-\left|\left\{i<\delta |d_i=d_{\delta }\right\}\right|.$$

Theorem 6.

For any graphic (non-zero) non-increasing degree sequence $\mathbf{d}$

$$\begin{array}{cc}\hfill {\nu }^{\ast }\left(\mathbf{d}\right)=max\{{\displaystyle \frac{1}{2}}\delta \in \mathbb{N}|& \sum _{i=1}^k{d}_i\le k^2+\sum _{i=k+1}^{n}min\{d_i-I_{i\le \delta },k\}\forall 1\le k<{\displaystyle \frac{1}{2}}\delta and\hfill \\ & \sum _{i=1}^k{d}_i+\left|\{i>\delta |d_i=d_{\delta }\}\right|\le k^2+\hfill \\ \hfill & +\sum _{i=k+1}^{n}min\{d_i-I_{d_i=d_{\delta }},k\}\mathrm{for}k=\delta +t_{\mathbf{d}}\left(\delta \right)\}\hfill \end{array}$$

(3)

where $I_X=1$ if X is true, otherwise $I_X=0$.

The proof of this complicated formula is based on algebraic manipulations of the Erdős–Gallai’s theorem, and it is shown in the Appendix A. Note, the remaining inequalities in Equation (3) can be quite complex from an analytical point of view. As the last result in this section, we provide a simple lower bound for ${\nu }^{\ast }\left(\mathbf{d}\right)$.

Theorem 7.

The size of the potentially maximum matching in a graphic sequence $\mathbf{d}$ is

$${\nu }^{\ast }\left(\mathbf{d}\right)\ge \underset{k=1,\dots ,n}{min}⌊k-1+{\displaystyle \frac{1}{2}}\left|\{i\mid k\le d_i\le d_k\}\right|⌋$$

(4)

Proof. 

For convenience, let

$$m^{\ast }=\underset{k=0,\dots ,n-1}{min}⌊k+{\displaystyle \frac{1}{2}}\left|\{i\mid k+1\le d_i\le d_{k+1}\}\right|⌋.$$

By Theorem 3, to deduce Equation (4), it is sufficient to prove that $d\circ \left(2m^{\ast }\right)$ is graphic. Note, that

$$m^{\ast }\le 0+{\displaystyle \frac{1}{2}}\left|\{i\mid 1\le d_i\le d_1\}\right|\le {\displaystyle \frac{1}{2}}n,$$

and $m^{\ast }$ is a clearly a positive integer. Since $\mathbf{d}$ is graphical, Theorem 5 applies. First, we distinguish three cases.

• For $k=n$, we have

  $$\begin{array}{cc}\hfill \sum _{i=1}^n{d}_i& \le n(n-1),\hfill \\ \hfill \sum _{i=1}^n{d}_i+2m^{\ast }<\sum _{i=1}^n{d}_i+2n& \le (n+1)n,\hfill \end{array}$$

  i.e., the $(n+1)$^th Erdős–Gallai inequality holds for $\mathbf{d}\circ \left(2m^{\ast }\right)$.
• If $2m^{\ast }\le d_k$, then

  $$\begin{array}{cc}\hfill \sum _{i=1}^k{d}_i& \le k(k-1)+\sum _{i=k+1}^{n}min\{d_i,k\},\hfill \\ \hfill \sum _{i=1}^k{d}_i& \le k(k-1)+min\{2m^{\ast },k\}+\sum _{i=k+1}^{n}min\{d_i,k\}.\hfill \end{array}$$
  The last inequality means that the k^th Erdős–Gallai inequality holds for $\mathbf{d}\circ \left(2m^{\ast }\right)$ if $2m^{\ast }\le d_k$ and $k\le n$.
• If $2m^{\ast }>d_{k+1}$ and $k<n$ is a jump locus of $\mathbf{d}$ then

  $$\begin{array}{cc}\hfill \sum _{i=1}^k{d}_i& \le k(k-1)+\sum _{i=k+1}^{n}min\{d_i,k\},\hfill \\ \hfill \sum _{i=1}^k{d}_i+2k& \le k(k+1)+\sum _{i=k+1}^{n}min\{d_i,k\},\hfill \\ \hfill \sum _{i=1}^k{d}_i+2k+\left|\{i\mid k+1\le d_i\le d_{k+1}\}\right|& \le k(k+1)+\sum _{i=k+1}^{n}min\{d_i,k+1\},\hfill \\ \hfill \sum _{i=1}^k{d}_i+2m^{\ast }& \le k(k+1)+\sum _{i=k+1}^{n}min\{d_i,k+1\}.\hfill \end{array}$$
  The last inequality is the $(k+1)$^th Erdős–Gallai inequality associated with $\mathbf{d}\circ \left(2m^{\ast }\right)$.

Note, that if $2m^{\ast }\ge d_k$ and $k+1$ is a jump locus of the non-increasing version of $\mathbf{d}\circ \left(2m^{\ast }\right)$, then k is a jump locus of $\mathbf{d}$. Therefore we have shown that the k^th Erdős–Gallai inequality holds for $\mathbf{d}\circ \left(2m^{\ast }\right)$ when

• $k=n+1$,
• $1\le k\le n$ and $2m^{\ast }\le d_k$,
• $2\le k\le n$ and $2m^{\ast }>d_k$ and k is a jump locus of the non-increasing version of $\mathbf{d}\circ \left(2m^{\ast }\right)$.

It remains to be shown that Equation (2) holds for $\mathbf{d}\circ \left(2m^{\ast }\right)$ with $k=1$ only when $2m^{\ast }>d_1$. By taking $k=0$ in the equation defining $m^{\ast }$, we obtain

$$\begin{array}{c}\hfill m^{\ast }\le 0+{\displaystyle \frac{1}{2}}\left|\{i\mid 1\le d_i\le d_1\}\right|\\ \hfill 2m^{\ast }\le \sum _{i=1}^{n}min\{d_i,1\}.\end{array}$$

Via Theorem 5, this concludes the proof that $\mathbf{d}\circ \left(2m^{\ast }\right)$ is graphic. □

3. Forcibly (0,1)-Factor Graphic Degree Sequences

In this section, we are looking for conditions on the degree sequence $\mathbf{d}$ which make it forcibly $\delta$-matching graphic (i.e., each realization of $\mathbf{d}$ should contain a $\delta$-matching).

3.1. How Big Must the Maximal Matching Be in Any Realization of a General Degree Sequence?

In this subsection, we will study the maximal forcible matching graphic property for general degree sequences. Recall that a matching is maximal if it is not fully contained by another matching.

For any matching M in a graph $G(V,E)$, let $V_M\subseteq V$ denote the set of matched vertices and let $U_M$ be the set of unmatched vertices. Clearly, $V_M\cup U_M=V$. Note that $|V_M|=2\left|M\right|$.

Proposition 1.

For any maximal matching M in graph G with no isolated vertices we have the following:

(i)

$$\sum _{v\in V_M}d\left(v\right)\ge \sum _{u\in U_M}d\left(u\right)+2\left|M\right|.$$

(5)

(ii)

$$\sum _{v\in V_M}d\left(v\right)\ge m\left(G\right)+\left|M\right|.$$

(6)

Proof. 

(i)

The vertices in $U_M$ are clearly independent. Furthermore, each edge incident with $u\in U_M$ must be incident with an $v\in V_M$. Finally M is completely within $V_M$.

(ii)

The next part follows immediately from (5) after adding to both sides ${\sum }_{v\in V_M}d\left(v\right)$ and observing that ${\sum }_{v\in V_M}d\left(v\right)+{\sum }_{v\in U_M}d\left(v\right)={\sum }_{v\in V}d\left(v\right)=2m\left(G\right)$.

□

We can now use this to obtain more concrete lower bounds on the LHS of (6). The simplest of these is the following:

Corollary 3

(First observed by Biedl, Demaine et. al. [5]). For any maximal matching M of a graph G:

$$\left|M\right|\ge {\displaystyle \frac{m\left(G\right)}{2\Delta \left(G\right)-1}}.$$

(7)

Proof. 

This follows immediately from (6) after noting that $2\left|M\right|\Delta \ge \sum _{v\in V_M}d\left(v\right)$. □

This statement means that if a matching is smaller than the RHS of (7), then the matching can be greedily extended to a bigger one. We remark that this proof is different from the proof in Biedl et al.’s work ([5] Theorem 7). The authors of that paper raised the following question (Section 5, Problem 2): “What can be said about the size of maximum matchings in graphs? Can we improve on bound (7)?” We offer answers in Theorems 8 and 12 below.

Theorem 8

(Maximality-bound). Let G be a graph without isolated vertices and with the non-increasing degree sequence $\mathbf{d}$. For any maximal matching M in G, we have

$$\left|M\right|\ge k^{\ast }=min\left\{k\in \mathbb{N}|\sum _{i=1}^{2k}{d}_i-m\left(G\right)-k\ge 0\right\}.$$

(8)

The degree sequence is forcibly $k^{\ast }$-matching graphic.

Proof. 

Let $r\left(k\right)={\sum }_{i=1}^{2k}{d}_i-m\left(G\right)-k$. Since every $d_i\ge 1$ and the degree sequence $\mathbf{d}$ is non-increasing, $r\left(k\right)$ is strictly monotone increasing. From Equation (6) it follows that for any maximal matching M of size k, we have

$$r\left(k\right)\ge \sum _{v\in \cup M}d\left(v\right)-m\left(G\right)-\left|M\right|\ge 0.$$

(9)

In other words, if $r\left(k\right)<0$, then there exists a matching of size at least $k+1$, which is equivalent to the statement. □

As we will see soon by Lemma 4, this affirmatively answers the question of the authors of [5], since this bound is stronger than the one in (7).

We also want to compare the strength of Theorem 8 with other known lower bounds. However, there are not many such results on the value of $\nu \left(\mathbf{d}\right)$ (without additional special structural requirements on G, like, e.g., being bipartite). We are aware of only two such results. The first one is based on Vizing’s seminal result on the chromatic index:

Theorem 9

(Vizing, 1964, [21]). For any simple graph G, the edge-chromatic number satisfies ${\chi }^{\prime }\left(G\right)\le \Delta \left(G\right)+1$.

The following lower bound then follows easily.

Corollary 4

(Vizing-bound).

$$\nu \left(G\right)\ge {\displaystyle \frac{m\left(G\right)}{\Delta \left(G\right)+1}}.$$

(10)

This approximation can be close to the actual value if the degree distribution is concentrated, but in case of heterogeneous degree sequences this can be vary far from being sharp. The Vizing-bound is better than inequality (7), but it only applies to maximum cardinality matchings, and not necessarily to all maximal matchings.

To describe the other known lower bound we will use the following notation: let $t_G\left(q\right)$ be the number of nodes in G whose degree does not exceed q.

Theorem 10

([2], Theorem 4.4). Let G be a simple graph on n nodes. Let

$$r\left(G\right):=min\left\{\ell \in {\mathbb{Z}}^{+}:\underset{0\le q<{\displaystyle \frac{n-\ell }{2}}}{max}\left(t_G\left(q\right)-q+1\right)\le \ell \right\}.$$

(11)

Then, G has a matching of size: $⌈{\displaystyle \frac{n-r\left(G\right)}{2}}⌉\le \nu \left(G\right)$.

We will call this result Pósa-bound, since in [2] it was proven using Pósa’s seminal Hamiltonian cycle result [22]. A slightly different form of this result was proven by Chvátal and Bondy already in ([9] Theorem 5.1) (using, essentially, Chvátal’s Hamiltonian cycle theorem). Inequality (11) has proven to be very useful for several DPG dynamics (such as the so-called linear DPG and MaxDPG) models. In a wide range of cases it provides much better estimates than the Vizing-bound, Equation (10).

Next, we give four toy degree sequence examples, illustrating the strengths of these three results (Theorem 8, Lemma 4 and Theorem 10), in comparison with previous bounds.

Example 1.

For ℓ-regular graphic degree sequence $\mathbf{d}$ on n nodes. (Clearly, there are a big many not isomorphic ℓ-regular graphs.) The maximality-bound (Theorem 8) yields

$$\nu \left(G\right)\ge {\displaystyle \frac{1}{2}}{\displaystyle \frac{\ell }{2\ell -1}}n,$$

(12)

while the Vizing-bound (Corollary 4) is almost sharp, since a “typical” (uniformly random) regular graph has $\nu \left(G\right)=n/2-O(logn)$ with high probability [23].

Example 2.

The well-known (non-bipartite) half-graph is defined as follows for every even n: let the set of vertices be the integers $1,\dots ,n$, and two distinct vertices i and j are joined by an edge $ij$ if and only if $i,j\le n/2$ or $i+n/2\le j$. (Clearly, this graph is unique.) The Pósa-bound (Theorem 10) gives the correct $\nu =n/2$, while the estimate given by the Vizing-bound is only $\sim n/4$, and the maximality-bound is also not any better either ($\sim {\displaystyle \frac{2-\sqrt{2}}{4}}n$).

Example 3.

In the well-known windmill graph $\mathit{Wd}(t,\ell )$, we have t copies of $K_{\ell }$ cliques, sharing one central vertex. The special case $\ell =3$: $\mathit{Wd}(t,3)$ is called the friendship graph. Clearly, the matching number is $\nu \left(\mathit{Wd}\right(t,3\left)\right)=t=(n-1)/2$ (near perfect matching, with one unmatched vertex). The maximality-bound implies that $\nu \left(\mathit{Wd}(t,3)\right)\ge ⌈{\displaystyle \frac{n+3}{6}}⌉$. The Vizing and Pósa estimates are constants.

Example 4.

For a general windmill graph $\mathit{Wd}(t,\ell )$ the Vizing-bound yields $\nu \left(\mathit{Wd}(t,\ell )\right)\ge {\displaystyle \frac{\ell -1}{2}}$, the Pósa-bound gives $\nu \ge \ell$, and the maximality-bound implies $\nu \ge {\displaystyle \frac{n-t+1}{4}}$.

In Example 1, the Vizing-bound is a factor of 2 better than the maximality-bound $k^{\ast }$ in Equation (8). However, this is a worst case scenario, as the next lemma shows. Moreover, the next lemma also shows that the maximality-bound is better than the bound of Corollary 3, i.e., that we positively answer the question raised by the authors in [5].

Lemma 4.

$${\displaystyle \frac{1}{2}}{\displaystyle \frac{m}{\Delta +1}}<{\displaystyle \frac{m}{2\Delta -1}}\le k^{\ast }$$

Proof. 

Recall from the proof of Theorem 8 the following notation: let $r\left(k\right)={\sum }_{i=1}^{2k}{d}_i-m\left(G\right)-k$ for a non-increasing degree sequence $\mathbf{d}$.

$$\begin{array}{cc}\hfill r\left(⌊{\displaystyle \frac{m}{2\Delta -1}}⌋\right)=\sum _{i=1}^{2\lfloor {\displaystyle \frac{m}{2\Delta -1}}\rfloor }{d}_i-m-⌊{\displaystyle \frac{m}{2\Delta -1}}⌋& \le \hfill \\ \hfill \le 2⌊{\displaystyle \frac{m}{2\Delta -1}}⌋·(\Delta -1/2)-m& \le 0.\hfill \end{array}$$

If any of the inequalities are strict, then it follows from the definition that $\lfloor {\displaystyle \frac{m}{2\Delta -1}}\rfloor <k^{\ast }$. If every inequality holds with equality, then ${\displaystyle \frac{m}{2\Delta -1}}$ is an integer and $r\left({\displaystyle \frac{m}{2\Delta -1}}-1\right)=1-2\Delta <0$, which also implies the statement. □

3.2. Strengthening the Maximality-Bound

In the remaining part of this paper, we will strengthen our maximality-bound for both maximal and maximum size matchings. Let us begin with maximal matchings.

In addition to inequality (8), we can study the derived subgraph $G[U,V]$, obtaining the following inequality system. This leads to a slightly stronger, but a computationally more complicated result than Theorem 8.

Lemma 5.

Let M be a maximal matching in G and let its degree sequence be $\mathbf{d}$. Then

$$\forall U\subseteq U_M\sum _{v\in V_M}min\{d\left(v\right)-1,|U\left|\right\}\ge \sum _{u\in U}d\left(u\right).$$

(13)

Proof. 

Since M is a maximal matching in G, $U_M$ must induce an empty graph in G. The number of edges incident on U is counted on the RHS of Equation (13). The set of edges incident on a vertex of U must be also incident on $V_M$. A vertex $v\in V_M$ is joined to at most $d\left(v\right)-1$ vertices of U, because the edge of M which is incident on v is not incident on $U_M$. Also, v is joined to at most $\left|U\right|$ vertices of U. Therefore, the RHS of Equation (13) is bounded by the sum of $min\left\{d\right(v)-1,|U\left|\right\}$ for all $v\in V_M$. (This inequality system is very similar to the one that appears in the well-known Gale–Ryser theorem, which fully describes the graphic bipartite degree sequences ([24,25]). □

We have the following result on the forcibly k-matching graphic problem.

Theorem 11.

The size of every maximal matching M in any realization of a non-increasing degree sequence $\mathbf{d}$ is at least

$$\left|M\right|\ge {\ell }^{\ast }=min\left\{\ell |\sum _{i=1}^{2\ell }min\{d_i-1,k\}\ge \sum _{i=2\ell +1}^{2\ell +k}{d}_i,\forall k=1,\dots ,n-2\ell \right\}.$$

(14)

Proof. 

By Lemma 5, Equation (13) holds. If $d\left(v\right)\le d\left(u\right)$ for $v\in V_M,u\in U_M$, then we can swap them between the LHS and RHS of (13) and the inequality will still hold. Thus, we have shown that $\left|M\right|\ge {\ell }^{\ast }$ must hold. □

For r-regular graphs $\left|M\right|\ge {\ell }^{\ast }=max\left({\displaystyle \frac{r}{2}},{\displaystyle \frac{r}{2r-1}}·{\displaystyle \frac{n}{2}}\right)$.

Now, we turn our attention to maximum matchings. Let one of them be M.

Lemma 6.

Let M be a maximum size matching in a graph G with degree sequence $\mathbf{d}$. Then

$$\sum _{uv\in M}max\left(d\left(u\right)-1,d\left(v\right)-1\right)+\left|\left\{uv\in M\left|d\right(u)=d(v)=2\right\}\right|\ge \sum _{w\in U_M}d\left(w\right)$$

(15)

Proof. 

For any $uv\in M$, if there exist two disjoint edges $e,f$ connecting $V_M$ to $U_M$ that both intersect $uv$, then we may take $M-uv+e+f$ to obtain a larger matching, contradicting that M is a maximum matching. Therefore if both u and v have neighbors in $U_M$, then there is exactly 1 such neighbor in $U_M$. In other words, the number of edges induced between $\{u,v\}$ and $U_M$ is

$$e\left(G[\{u,v\},U_M]\right)\le max\left\{d\left(u\right)-1,d\left(v\right)-1,min\left\{2,d\left(u\right)+d\left(v\right)-2\right\}\right\}.$$

(16)

The max on the right-hand side takes its value from the third argument exclusively only if $d\left(u\right)=d\left(v\right)=2$. Summing inequality (16) over every $uv\in M$, we obtain inequality (15). □

Using inequality (15), we can strengthen Theorem 8 as follows:

Theorem 12

(Lower bound on the matching number). For any graph G with non-increasing degree sequence $\mathbf{d}$ we have

$$\nu \left(G\right)\ge min\left\{k\ge 0|\sum _{i=1}^{k}2d_i+\sum _{i=k+1}^{2k}{d}_i\ge 2m\left(G\right)\right\}.$$

(17)

Proof. 

Let M be a maximum matching in G, and let $k=\left|M\right|$. Adding ${\sum }_{w\in V_M}d\left(w\right)$ to both sides of inequality (15) and performing usual algebraic manipulations we obtain:

$$\sum _{i=1}^{k}2d_i+\sum _{i=k+1}^{2k}{d}_i\ge 2m\left(G\right).$$

(18)

□

Note, inequality (17) is not always better than the maximality-bound (8). For example, for the friendship graph we have $k\ge (t+2)/3$. However, for the general windmill graph $\mathit{Wd}(t,\ell )$ we have

$$k\ge {\displaystyle \frac{t(\ell -2)+2}{3}}={\displaystyle \frac{n-t+1}{3}}$$

This is a factor of ${\displaystyle \frac{4}{3}}$ larger than the maximality-bound on the same degree sequence.

For the half-graph for an even n, we have

$$6kn-5k^2-3k\ge n^2\Rightarrow mink\simeq {\displaystyle \frac{n}{5}}.$$

Finally, for an ℓ-regular graph G, we have $\nu \left(G\right)\ge {\displaystyle \frac{1}{3}}n$. The lower bound is sharp for disjoint union of triangles, and it is a factor of ${\displaystyle \frac{4}{3}}$ better than what we obtained from Theorem 8. In comparison, ([26], Theorem B) proves $\nu \left(G\right)\ge {\displaystyle \frac{4n-1}{9}}$ for any connected 3-regular graph G on n vertices. Of course, for disconnected graphs, the matching number can be lower: for any 5-divisible n, we have $\nu \left({\displaystyle \frac{n}{5}}\times K_5\right)={\displaystyle \frac{2n}{5}}$.

4. Conclusions and an Open Problem: Minimum Maximum Matching

In summary, we presented novel results that explore the connections between the matching number of a simple graph and its degree sequence. We provided lower bounds for the size of the largest possible matching number among all the realizations of a given degree sequence and provided estimates for the minimum size of both the maximal and the maximum matchings, as constrained by the degree sequence, independently of graphical realizations, answering a question that was open since 2004 [5]. Understanding the connections between matchings and degree sequence is important in at least two areas in network science: 1. in network growth models where the incoming vertex that joins the graph may pinch together several independent edges to form its connections, for example in degree-preserving network growth [1,2] and 2. in network control [27]. Additionally, it has potential applications in connections between graph theory and the theory of primes [3].

We finish this paper with an open problem. A graph G can have several maximal matchings. Let us denote the smallest size among the maximal matchings with $\overline{\nu }\left(G\right)$ and thus $\overline{\nu }\left(G\right)\le \left|M\right|\le \nu \left(G\right)$ for any maximal matching M. In general, it was showed in [28] that to determine the value $\overline{\nu }\left(G\right)$ is NP-hard. The same is true for several restricted graph classes. Since $2\overline{\nu }\left(G\right)\ge \nu \left(G\right)$ therefore a 2-approximation is trivial. However, Chlebík and Chlebíková showed ([29]), that a $7/6$ approximation algorithm for the value $\overline{\nu }\left(G\right)$ is also NP-hard. Let $\overline{\nu }\left(\mathbf{d}\right)$ denote the minimum possible $\overline{\nu }\left(G\right)$ for all possible realizations of the graphic degree sequence $\mathbf{d}$. It seems to be an interesting question is whether $\overline{\nu }\left(\mathbf{d}\right)={\ell }^{\ast }\left(\mathbf{d}\right)$ (see inequality (14)).

For any positive integer t, let us consider the following degree sequence: $\mathbf{h}=({(2t-1)}^{2t},1^{2t(2t-1)})$ (the number of vertices is $n=4t^2$). Then (14) gives

$$\overline{\nu }\left(\mathbf{h}\right)\ge {\ell }^{\ast }\left(\mathbf{h}\right)=2t$$

Let $G_1=K_{2t}+t(2t-1)\times K_2$ and $G_2=2t\times K_{1,2t-1}$, both realizations of $\mathbf{h}$. We have $\nu \left(G_1\right)=2t^2$ and $\nu \left(G_2\right)=2t$, so ${\ell }^{\ast }\left(\mathbf{h}\right)$ is indeed equal to $\overline{\nu }\left(\mathbf{h}\right)$, even though $\mathbf{h}$ is potentially perfectly matchable. We also conjecture that

$${\nu }^{\ast }\left(\mathbf{d}\right)\le {\displaystyle \frac{1}{2}}{\overline{\nu }\left(\mathbf{d}\right)}^2$$

(19)

holds for any degree sequence $\mathbf{d}$. The degree sequence $\mathbf{h}$ shows that (19) is potentially sharp.