WorksComputer Science
Degree Realization with Maximum Matching
Abstract
The Maximum Matching Degree Realization problem requires, for a sequence of positive integers, to compute a realizing graph(whose degree sequence corresponds to ) with the maximum possible matching. We present a polynomial-time algorithm for this problem. The decision version of this problem requires to determine whether a sequence admits a realization with a matching of size (without computing such a realization). Recently, it was shown that it can be done by verifying a series of inequalities. We improve the existing characterization by reducing the number of inequalities.
Introduction
The Degree Realization (DR) problem requires to decide, for a given non-increasing sequence of positive integers, if there exists some -vertex (simple undirected) graph such that for every , and to construct such a graph if it exists. Such a sequence is called graphic.
Two central questions on realizations concern characterizations (i.e., necessary and sufficient conditions) for a sequence to be graphic, and efficient algorithms for finding realizing graphs. A necessary and sufficient condition for a given sequence of integers to be graphic (also implying an decision algorithm) was presented by Erdős and Gallai [7]. Havel [16] and Hakimi [15] described an -time algorithm that given a sequence of integers proves that the given sequence is not graphic or computes an -edge graph realizing it, where .
Here, we study the variant of the problem where, given a sequence with possibly many realizing graphs, the goal is to find a realizing graph that also optimizes some quality measure. Hereafter, we refer to such problems as optimized realization problems. Concretely, we consider the classical Maximum Matching (MM) problem. For a graph , a matching is an edge set , such that and do not share a vertex, for every two distinct . The size of the maximum matching in is denoted by
Given a graphic sequence , we look for a realizing graph with the maximum possible matching. For example, for , a realization consisting of a 6-vertex cycle is better that a realization consisting of two triangles, since whereas . The resulting optimized realization problem is formally defined as follows. Letting
the MM Degree Realization (MM-DR) problem requires finding a realizing graph attaining .
Similarly, one may define optimized realization problems for other graph optimization problems, such as Maximum Clique, Maximum Independent Set, Minimum Vertex Cover, and Minimum Dominating Set. Their optimal values on a given graph are defined as , , , and , respectively. The corresponding optimized realization problems on degree sequences are named Maximum Clique Degree Realization (MC-DR), MIS Degree Realization (MIS-DR), MVC Degree Realization (MVC-DR), and MDS Degree Realization (MDS-DR), and their optimal values on a given are denoted by , , , and , respectively.
Interestingly, while the graph versions of most of these optimization problems are NP-hard, the optimized realization versions of MC, MIS, MVC, and MDS have been shown to be polynomial-time solvable. Rao [24] gave a characterization of sequences realizable by a graph containing a clique of size . This result was based on a phenomenon known as the prefix lemma, which for MC says that if has a realization containing , then it has a realization such that the vertices of maximum degree induce a clique . This result implies a polynomial-time algorithm for MC-DR (see, e.g., [13]). Consequently, it follows readily that polynomial-time algorithms also exist for MIS-DR and MVC-DR. Note that a prefix lemma also applies to MVC. This prefix property is satisfied by MDS [13], and it was recently used to obtain a characterization and a realization algorithm for MDS-DR [3].
As for MM-DR, the prefix property is satisfied also by MM [14]. Moreover, due to this property, MM() can be computed efficiently using a result by Kundu [19] (see details below). However, so far it was not known how to exploit this property in order to derive a polynomial-time algorithm for MM-DR. This problem was handled for some restricted graph families in [5], but the general problem was left open.
Recently, Erdős et al. [9] studied MM-DR. Given a sequence and an integer , they presented an Erdős–Gallai type characterization, based on a system of inequalities, which is satisfied if and only if has a realization with a matching of size . Applying these characterizations to a given degree sequence, the maximum size of a matching can be computed efficiently, although a specific realization is not provided.
Our Results
Here, we present a polynomial-time realization algorithm for MM-DR. Our algorithm makes use of a stronger version of an existing prefix lemma for general graphs [14], termed the inverted prefix lemma, established in the current paper. This lemma is analogous to the inverted prefix lemma established in [5] for bipartite realizations of two sequences (or a bi-sequence). We also utilize an algorithm due to Fulkerson, Hoffman and McAndrew [11] for a special case of the -factor problem (discussed later), which is based on the following three phases:
Realization of the bi-sequence by a bipartite graph ,
Conversion of to a half-integral general (non-bipartite) realization for , where in a half-integral realization an edge with weight half contributes half to the degree of its end-points.
Rounding to an integral general realization .
In addition, we show how the described method leads to the characterization recently proved by Erdős et al. [9]. In fact, we show that one of the equations in the characterization is redundant.
Related Work
Several papers studied network realization with a given subgraph. Kundu [19] showed that the sequences and the component-wise difference , such that and (component-wise), are graphic only if there exists a graph realizing that has a subgraph realizing . This result can be used to decide whether MM() , for a given , by checking . Furthermore, MM() can be computed efficiently, since MM() is the maximum , such that is realizable. This result can also be used to decide whether a given sequence has a perfect matching by assigning , for every . Kleitman and Wang [18] gave an algorithm for computing a realization of that contains a subgraph which realizes . Their algorithm can be used to compute a realization of that contains a perfect matching, if such a realization exists. Extensions of the above result were presented in [18, 21].
Rao and Rao [23] and Kundu [19] gave a characterization of sequences that can be realized by a Hamiltonian graph. Chungphaisan [6] gave an algorithm, that given a sequence , constructs a realization with a Hamiltonian cycle (or path), if such a realization exists. Rao [24] characterized sequences that can be realized by a graph containing (a clique of size ). This result was based on on the Prefix Lemma for MC. An alternative proof was given in [17], and a constructive proof was presented in [26]. It follows that MC-DR can be solved in polynomial time by checking if has a realization containing , for .
Gould, Jackson and Lehel [14] extended Rao’s result by showing that if has a realization containing as a subgraph (but not necessarily an induced sub-graph), then there exists a realization of containing where the vertices of have the largest degrees. Yin [25] used this to extend Rao’s result [24] by giving a characterization of graphic sequences that contains a split graph composed of a clique is of size and an independent set of size . (Observe that is a clique of size .)
Gentner, Henning and Rautenbach [13] studied MIS-DR and MDS-DR. They proved the prefix lemma for MDS-DR and gave a realization algorithm for MDS-DR on sequences with , leaving the general case open. They also provided characterizations for MIS-DR and MDS-DR in forests. Gentner, Henning and Rautenbach [12] gave characterizations to realizations that minimize the maximum size of an independent set and that maximize the minimum size of a dominating set in forests. Recently, Bar-Noy et al. [3] gave a characterization and a realization algorithm for MDS-DR in general graphs.
Bock and Rautenbach [5] studied MM-DR in trees and bipartite graphs, where the partition is given. Their result on bipartite graphs is also based on a stronger version of the prefix lemma, which is essentially an inverted prefix lemma for bipartite graphs.
Fulkerson, Hoffman and McAndrew [11] provided a characterization for the realizability of a sequence with respect to multi-graphs that satisfy the odd cycle condition (discussed later). Building on the result of [11], Kundu [20] presented conditions for the factorization of graphs that satisfy the odd cycle condition. Anstee relied on the technique of [11] to obtain an algorithmic proof of the -factor theorem [1] and a simplified characterization for the existence of a -factor for special cases [2]. The result of Yin [25], mentioned above, was also based on [11]. The results for MDS-DR [3] are also based on this technique.
Inverted Prefix Lemma
In this section, we establish the inverted prefix lemma. Recall that Gould, Jacobson and Lehel [14] gave a general prefix lemma that applies to any subgraph. In the following lemma we provide the special case of a matching.
Lemma 2.1 (Arbitrary Prefix Lemma for MM [14]). If a sequence has a realization with a matching of size , then has a realization with a matching of the same size such that vertices participating in the matching have the highest degrees in , i.e., .
For our purposes, however, we need a stronger type of prefix lemma, similar to the one used in [5] for solving MM-DR over bipartite graphs. Towards proving this stronger claim, we introduce some notation. Consider a realization of a degree sequence , with four vertices such that and . Then the FLIP operation transforms into a graph by replacing the former two edges with the latter two, i.e., setting
This operation preserves the degrees of individual vertices, but could lead to non-isomorphic realization. It was widely studied and used in different contexts, see [10, 8, 4]. Finally, define , for and for an integer .
Lemma 2.2. Let be a realization of with , such that for every . If there is a matching covering the first vertices , then there is a realization of with the "inverted" matching
such that .
Proof. Call the pair valid if is defined on with , , and is on . Consider a valid pair and let
and . If , then , and we are done.
We describe procedure Invert that given a valid pair violating the claim produces a new valid pair , such that either satisfies the claim or . Repeatedly applying Invert gradually modifies while preserving validity and strictly increasing . Since is bounded above by , the process terminates in at most steps and the obtained pair satisfies the claim.
Given a pair not satisfying the claim, let and . Since , there are edges , and the involved vertices satisfy and by the definition of . Let
If there is a realization such that , then the pair is valid and either satisfies the claim or increases . Proceed according to one of the following cases to obtain . See Figure 1.
Figure 1. Illustration of the cases in the proof of Lemma 2.2. All the illustrating figures maintain the convention that solid lines represent edges existing in the graph and dashed lines represent edges not in the graph.
Case 1: .
Then simply take .
Case 2: .
Then perform a FLIP operation on replacing with . obtained in this way satisfies .
Case 3: and .
Then there is a vertex , such that and . Indeed, and is connected to , but not to , so there exists compensating for this. Obtain by doing a FLIP replacing with .
Case 4: and .
Then there is a vertex , such that and . Similarly to the previous case, this is because . Obtain by doing a FLIP replacing with .
The lemma follows.
Combining Lemma 2.1 and Lemma 2.2 gives a more specific Prefix Lemma for Maximum Matching.
Lemma 2.3 (Inverted Prefix Lemma for MM). If a sequence has a realization where such that for every , with a matching of size , then has a realization with the matching .
Algorithm for Realization with Maximum Matching
Fulkerson, Hoffman and McAndrew [11] presented an algorithm for a special case of the -factor problem. More specifically, they considered the following degree realization problem. Let be a sequence, and let be a symmetric integral matrix. Intuitively, one can think of as representing a multigraph over with parallel edges between and for every . Fulkerson et al. [11] studied the problem of finding a multigraph , such that and the number of parallel edges between and is bounded above by . Intuitively, the sought realizing multigraph needs to be a sub-multigraph, or factor, of . We refer to such a realization as a realization of with respect to .
Let be a graph derived from , where
That is, is obtained from by replacing all multiedges by edges.
The matrix is said to satisfy the odd-cycle condition if and only if the distance between any two disjoint odd cycles in the derived graph is at most one. In other words, any two disjoint odd cycles in must be connected by an edge.
Fulkerson et al. [11] presented a characterization for the realizability of a sequence with respect to that satisfies the odd-cycle condition. Their proof is constructive in the sense that it implies a realization algorithm for instances, where satisfies the odd-cycle condition. The details of this algorithm for the specific context of realization with maximum matching are given in § 4.
Theorem 3.1 ([11]). Let be a sequence of size , and let be a symmetric integral matrix. There exists a polynomial-time algorithm that computes a realization of with respect to or determine that there is no such realization, assuming that satisfies the odd-cycle condition.
We show that we can use Theorem 3.1 to obtain a realization algorithm for MM-DR with a matching of size .
Given a sequence , our first step is to compute using the Erdős-Gallai type characterization of Erdős et al. [9].
Next, Based on the Inverted Prefix Lemma (Lemma 2.3), we construct an instance and as follows:
Observation 3.2. There is a realization of with a matching of size if and only if there is a realization of with respect to .
Observation 3.3 (Odd-cycle condition). satisfies the odd-cycle condition. That is, for any pair of disjoint odd cycles in , there exist and , such that .
Proof. Let , be arbitrary vertices. If , then let be any other vertex in . Otherwise, let .
This implies the following.
Theorem 3.4. There exists a polynomial-time algorithm for constructing a realization of a given graphic sequence that also has a matching of maximum size (among all possible realizations of ).
Detailed Realization Algorithm
In this section we present the full details of the realization algorithm that was mentioned in the previous section. The algorithm proceeds in several steps, presented in the coming subsections. First, the algorithm computes using the Arbitrary Prefix Lemma (Lemma 2.1) and Kundu’s result [19]. Next, the MM-DR problem over general graph is reduced to the same problem over bipartite graphs, by applying the realization algorithm of Fulkerson et al. [11] while ensuring preservation of a matching. Then, MM-DR over bipartite graphs is reduced to a maximum flow problem. To be more specific, given the size of the maximum matching and a degree sequence pair , we construct a bipartite flow graph , such that if the maximum flow attained in equals , then it corresponds to a realization of with a matching of size . (This is where we make use of the Inverted Prefix Lemma 2.3.) The next step is to convert to a half integral general (non-bipartite) realization for . Finally, is rounded to an integral general realization .
Computation of MM (d)
As mentioned before, given a candidate value , one can check whether by using the result of Kundu [19] with . That can be done in time using [7]. Hence, can be computed in time using binary search.
Reduction to a Bipartite Sequence Pair
Given a sequence , a bipartite graph , where and , is a -matched realization for the bi-sequence, if it satisfies the properties:
(M1) realizes the sequence pair .
(M2) for every .
(M3) .
First, we describe an algorithm that given a -matched realization of , produces a graph realizing with a matching of size .
Compute a half-integral solution.
(a) For all , let
(b) Define a weighted graph with vertex set and an edge of weight for every . Clearly, is half-integral.
(c) Let be the inverted matching in . According to (M3)
(d) Define the weighted degree of a vertex to be
Note that realizes in the weighted sense, namely,
Preparing for discarding non-integral weights while keeping the degrees unchanged. Construct a graph obtained by removing from the edges of integral weight and keeping only those of weight . Formally, and .
In later stages of the construction, whenever is modified (by changing the weight of some edge from to 0 or 1), is modified accordingly (by removing the edge ).
Partition into cycles.
(a) Partition the edge set of into disjoint (not necessarily simple) cycles each covering an entire connected component of the graph. Since is an even graph by Observation 4.1, this can be done in polynomial number of steps.
(b) Let be a set of cycles in the partition.
(c) Let , .
Eliminate even cycles.
For every cycle , do the following.
(a) Traverse starting from an arbitrary vertex and continuing along the cycle until returning to . Denote the resulting sequence of edges by .
(b) Increase (resp., decrease) edge weights on even (resp., odd) positions in the sequence by . That is, for every , is set to if is even and otherwise. (This does not change the weighted degrees in and does not affect other cycles in or edges in .)
Eliminate odd cycles.
Arrange the cycles in in pairs (by Observation 4.2 their number is even). For every pair of cycles choose vertices , according to Observation 4.3. Then do the following.
(a) Starting from , traverse via edges . Starting from vertex , traverse via edges .
(b) Let (by Observation 4.3, this weight must be either or ).
(c) Set .
(d) For every and , modify the edge weights in the cycles and as follows:
By Observation 4.4, at this stage each edge in has weight or , realizes , and (1) holds.
Generate the output .
Transform into a simple graph , with an edge whenever in . Note that forms a matching in by (1).
The algorithm is justified by the following Observations.
Observation 4.1. The graph is even (i.e., all its vertex degrees are even).
A connected even graph has an Euler cycle, implying the following.
Observation 4.2. The number of cycles in is even.
Proof. Observe that , where is the number of edges, which is an integer. Therefore, the number of edges with weight must be even. Since the cycles in cover all of and are disjoint, the observation follows.
The following observation is implied by Observation 3.3.
Observation 4.3. For any pair of disjoint odd cycles , there exist and , such that and .
Proof. Observation 3.3 implies that for any pair of disjoint odd cycles , there exist and , such that .
Assume, towards contradiction, that . Then the edge belongs to , implying that and belong to the same connected component in . But this contradicts the fact that and where and cover different connected components of .
Observation 4.4. At the end of Step 5, each edge in has weight 1 or 0, realizes and Eq. (1) holds.
Proof. After Step 5, contains no more edges of weight . Moreover, neither of the modifications performed in Step 5 change the weighted degrees in , affect other cycles in or edges in . The observation follows.
The reduction correctness follows from the next lemma.
Lemma 4.5. There exists a -matched realization of the bi-sequence if and only if .
Proof. If there is a -matched realization of , then the aforementioned algorithm produces a realization of with a matching of size .
For the other direction, given a realization of with vertices and a matching of size , there is a realization with a matching by the Inverted Prefix Lemma (Lemma 2.3). Consider the following graph with , and if and only if . Clearly, realizes and for every , so it satisfies (M1) and (M2). Moreover, the set is a matching of size in satisfying (M3). Indeed, since is a matching, the edges in form a matching too and each edge leads to two edges . The lemma follows.
Reduction to Flow
According to the previous section (in particular, Lemma 4.5) given a degree sequence all we need is to find a bipartite -matched realization of for maximum possible . Next we describe how to construct a flow graph for any , such that -matched realization of exist if and only if the maximum flow in is . Moreover, given an integer flow of this value we describe how to construct a desired realization.
First we describe the construction of . The node set contains nodes (for ), corresponding to the vertices of , and the source is connected to them. Similarly, the node set contains nodes (for ), corresponding to the vertices in , and these are connected to the sink . The nodes are organized into the following sets:
Candidates for the matching:
and ,
Rest of the nodes:
and ,
Source and sink: .
The edges are capacitated and directed from left to right, i.e., an edge leads from the node to the node and can carry up to units of flow. The source has edges leading to every node , with capacity for and for . Similarly, there are edges leading from every node to the sink , with capacity for and for . This enforces the degree constraint for the vertices and in . Finally, there’s a unit capacity edge for every , such that and . Overall, the edge set of the flow graph is structured as a complete biclique minus an inverted matching and minus diagonal edges, with a source connected to and a sink connected to . Formally, (along with the edge weights) is defined as follows:
The network is schematically depictured in Figure 2, dashed edges indicate forbidden matching and forbidden diagonal edges. The construction is justified by the following Lemma 4.6.

Figure 2. The flow network . Solid arcs are labeled by their capacities. Dashed lines indicate forbidden pairs. The middle arcs , present exactly when and , all have capacity 1 and are omitted for clarity.
Lemma 4.6. There exists a -matched bipartite graph that realizes the if and only if the value of a maximum flow in is equal to .
Proof. Suppose the maximum value of an flow in is . Using integral flow theorem, we assume that the maximum flow is integral. Denote a value of the flow from a vertex to a vertex by . Define the bipartite graph as follows:
For each node , create a corresponding node .
For each node , create a corresponding node .
For every , if , then create an edge and add it to .
For every create an edge and add it to .
It remains to verify that correctly realizes and is -matched. The degree of in equals to the number of edges that carry flow if and one more than the corresponding flow if . Since conserves flow, and since all the edges are saturated, . Similarly, for every , so satisfies (M1). Since does not have edges for any , it follows that does not have edges , satisfying (M2). Finally, the matching was added in step 4, so satisfies (M3).
Conversely, suppose , where and , is a -matched bipartite graph realizing with the matching . We need to define a flow function on and prove that its value equals . Since the sum of capacities of outgoing edges from is exactly this sum, maximum flow cannot exceed it, thus it is enough to construct a flow with the aforementioned value.
Saturate Edges from Source and to Sink:
Flow Through Edges:
For every and such that , set ,
Completing the flow function:
Set the flows of all other edges to 0.
We need to argue that the defined flow is legal. Note that by construction, the total flow out of the source is and the total flow into the sink is . It remains to verify that for every vertex except and , the incoming and outgoing flows are equal.
Node : By construction, the incoming flow at is if and if . As for the outgoing flow, recall that there are exactly indices for which if and such indices if . Hence, conserves flow.
Node : By construction, the outgoing flow at is if and if . As for the incoming flow, recall that there are exactly indices for which if and such indices if . Hence, conserves flow.
The claim follows.
We conclude the section with the following result.
Theorem 4.7. There exists an time algorithm for constructing a realization of a given graphic sequence that also has a matching of maximum size (among all possible realizations of ).
Proof. As was shown in the beginning of this section a maximum size of a matching can be found in a running time of . As for the realization algorithm, given , to find a -matched realization of we first build the flow graph and find a maximum - flow in it. Since has vertices and edges, a maximum flow can be computed in time using the maximum flow algorithm by Orlin [22]. Given a maximum flow, adjacency matrix for -matched bipartite realization for the sequence pair can be computed in time. Next we go through all the steps of transformation of into -matched realization for and show that each step takes time.
Step 1: The adjacency matrix of the weighted graph can be computed from the adjacency matrix of in .
Step 2: It takes to compute the adjacency matrix of using the adjacency matrix of .
Step 3: Since an Eulerian cycle can be found by linear time in the number of edges and is an even graph, a partition of into disjoint cycles takes time.
Step 4: Separating even cycles in and applying the corresponding modification to them takes time.
Step 5: For every pair of odd cycles it takes constant time to find vertices and satisfying Observation 4.3 following the proof of Observation 3.3. Given and it takes linear time to apply corresponding modifications. Therefore, the complexity for all pairs of cycles is .
Step 6: At this step does not have edges of weight , so it can be transformed into in time.
The theorem follows.
Characterization
This section considers the characterization of of a given sequence . A characterization for this problem was recently given by Erdős et al. [9] and contains inequalities (see Theorem 5.1). In previous Sections the realization problem was reduced to a flow problem using the method developed by Fulkerson et al. [11]. We show that this technique not only leads to constructive algorithm, but also to an alternative proof of the characterization and show that one of its inequalities is redundant.
Theorem 5.1 (Theorem 2.13, [9]). For a graphic positive non-increasing degree sequence and an integer let
There exists a realization of with a matching of size if and only if:
For a degree sequence , Lemmas 4.5 and 4.6 imply that if and only if the maximum - flow in has value . Let denote the capacity of an - cut in this network. The total capacity leaving is . Hence, by the max-flow min-cut theorem, the required flow exists if and only if for every - cut. We show that these cut constraints reduce to the first family of inequalities in Theorem 5.1. Thus, the additional inequality in that characterization is redundant.
Theorem 5.2. Let be a graphic sequence, and let . Define for and for There exists a realization of with a matching of size if and only if
The case is immediate. Throughout the proof, , , and satisfy the assumptions and definitions of Theorem 5.2, and an interval with no indices denotes the empty set. We first rewrite the cut constraints and then reduce the number of inequalities that must be checked. For an - cut , define the index sets
These sets determine the cut: , and is its complement. Summing the capacities of the edges from to gives the following lemma.
Lemma 5.3. Every - cut in satisfies if and only if
where denotes the number of edges from to in .
For each fixed , we next minimize over to obtain a single inequality.
Proof. Since and , rearranging (3) gives
We first show that it suffices to consider disjoint sets and . For arbitrary , let and . Then and . Moreover,
where the second equality uses the symmetry of the allowed pairs in and the third uses the fact that . Thus, (3) holds for all if and only if
For disjoint , the definition of gives
Substituting this identity and the definition of into the preceding cut inequality yields
Equivalently,
It remains to minimize the right-hand side over . Let
Including in contributes to the right-hand side; excluding it contributes 0. Hence, minimizing the right hand side is equivalent to
This is the required inequality.
The first two terms on the right-hand side in Lemma 5.4 give the usual degree-sum bound in the Erdős–Gallai Theorem. The subtracted term accounts for the prescribed matching. Accordingly, define, for every ,
Since is graphic, the degree-sum bound gives for every . By Lemma 5.4, the cut constraints are therefore equivalent to for every .
Lemma 5.5. Under the assumptions of Theorem 5.2, inequalities (2) imply , for every integer .
Proof. We consider three cases.
Case 1: If , then , since is graphic.
Case 2: If , each pair with intersects . Thus, , and Case 1 applies.
Case 3: Suppose and . Some index then satisfies . Since is non-increasing, the last degrees are all at most , as well. Consequently, . Using when , and otherwise, inequality (2) becomes
This is exactly .
We can now prove the characterization, namely Theorem 5.2. Proof of Theorem 5.2. Suppose first that has a realization with a matching of size . By the Inverted Prefix Lemma (Lemma 2.3), there is a realization containing the inverted matching on the first vertices. Deleting these matching edges gives a realization of . By the Erdős–Gallai Theorem,
Substituting for gives (2).
Conversely, suppose that (2) holds. By the flow equivalence and Lemmas 5.3 and 5.4, it suffices to prove that for every . Suppose, towards a contradiction, that some set satisfies . Choose such a set of minimum cardinality, and let . Since all degrees are positive, , so .
First, we show that for every . Otherwise, choose with . Then
Lowering the cardinality threshold from to can remove from the set counted by only indices of degree outside . Removing from cannot cause any further loss. Hence, . It follows that , contradicting the minimality of .
Next, suppose that and satisfy , and let . Since , we have . Also, , so is not counted by . Replacing by can remove at most the index from the set counted by . Thus , and . Repeating this replacement, we may assume that the degrees indexed by are , counted with multiplicities. In particular, . Indices of degree may still be chosen arbitrarily, so need not hold.
We have and next show that . Suppose that . Every index outside then has degree at most . The indices counted by occur in pairs , so is even. Moreover,
Since is graphic, its degree sum is even. Thus is even, and implies . Choose with . As in the first step,
Also, . Therefore, , again contradicting minimality.
Let and , and put . We have . The value of is unchanged by replacing indices within the block . Since every degree indexed by exceeds ,
The indices satisfying form a prefix of . Hence, replacing by can only decrease the second cardinality. This leaves unchanged and cannot decrease or . We may therefore assume that .
For , define , so . Let . Since , we have . We show that by estimating the successive differences. For , the new index has degree and is not counted by . Adding it can remove at most its partner from the set counted by . Increasing the threshold from to can add only indices of degree . Consequently,
For the same range of , put . Every index in has degree at least , and therefore
Applying the upper bound on gives . Hence, for ,
Here , and minimality gives . Since these values are integers, . Summing the differences yields .
Finally, consider two cases.
Case 1: If , then and . By Lemma 5.5, , a contradiction.
Case 2: If , the preceding bound at gives
The second inequality holds because all indices in have degree at least . This again contradicts .
Thus for every , completing the proof.
AI Disclosure
Chat-GPT-6 Astra was used to generate an initial version of the proof of Theorem 5.2, which was then simplified and rewritten by us. The tool was also used to help with the drawing of Figure 2, for spell checking and to enhance readability throughout the paper. We verified the correctness and originality of all content including references.
References
- [1]R. P. Anstee. An algorithmic proof of Tutte’s f-factor theorem. J. Alg., 6(1):112–131, 1985.DOI
- [2]R. P. Anstee. Simplified existence theorems for (g,f)-factors. Discr. Appl. Math., 27(1-2):29–38, 1990.DOI
- [3]A. Bar-Noy, I. Kalinichev, D. Peleg, and D. Rawitz. Degree realization with minimum dominating set. In 27th IPCO, volume 16588 of LNCS, pages 64–80, 2026.
- [4]M. D. Barrus. On realization graphs of degree sequences. Discrete Mathematics, 339(8):2146–2152, 2016.DOI
- [5]F. Bock and D. Rautenbach. On matching numbers of tree and bipartite degree sequences. Discr. Math., 342(6):1687–1695, 2019.DOI
- [6]V. Chungphaisan. Construction of hamiltonian graphs and bigraphs with prescribed degrees. J. Comb. Theory B, 24(2):154–163, 1978.DOI
- [7]P. Erdős and T. Gallai. Graphs with prescribed degrees of vertices [Hungarian]. Matematikai Lapok, 11:264–274, 1960.
- [8]P. L. Erdős, Z. Kiraly, and I. Miklos. On the swap-distances of different realizations of a graphical degree sequence. Combinatorics, Probability and Computing, 22:366–383, 2013.DOI
- [9]P. L. Erdős, S. R. Kharel, T. R. Mezei, and Z. Toroczkai. New results on graph matching from degree-preserving growth. Mathematics, 12(22), 2024.DOI
- [10]D. Fulkerson. Zero-one matrices with zero trace. Pacific J. Math., 10:831–836, 1960.DOI
- [11]D. R. Fulkerson, A. J. Hoffman, and M. H. McAndrew. Some properties of graphs with multiple edges. Canad. J. Math., 17:166–177, 1965.
- [12]M. Gentner, M. A. Henning, and D. Rautenbach. Largest domination number and smallest independence number of forests with given degree sequence. Discr. Appl. Math., 206:181–187, 2016.
- [13]M. Gentner, M. A. Henning, and D. Rautenbach. Smallest domination number and largest independence number of graphs and forests with given degree sequence. J. Graph Theory, 88(1):131–145, 2018.
- [14]R. J. Gould, M. S. Jacobson, and J. Lehel. Potentially G-graphical degree sequences. In Combinatorics, Graph Theory, and Algorithms, volume 1, pages 451–460, 1999.
- [15]S. L. Hakimi. On realizability of a set of integers as degrees of the vertices of a linear graph – I. SIAM J. Appl. Math., 10(3):496–506, 1962.DOI
- [16]V. Havel. A remark on the existence of finite graphs. Casopis Pest. Mat., 80:477–480, 1955.DOI
- [17]A. Kézdy and J. Lehel. Degree sequences of graphs with prescribed clique size. In Graph Theory, Combinatorics, Algorithms, and Applications, pages 535–544, 1999.
- [18]D. J. Kleitman and D. L. Wang. Algorithms for constructing graphs and digraphs with given valences and factors. Discr. Math., 6:79–88, 1973.DOI
- [19]S. Kundu. The k-factor conjecture is true. Discr. Math., 6(4):367–376, 1973.DOI
- [20]S. Kundu. A factorization theorem for a certain class of graphs. Discr. Math., 8(1):41–47, 1974.DOI
- [21]S. Kundu. Generalizations of the k-factor theorem. Discr. Math., 9(2):173–179, 1974.DOI
- [22]J. B. Orlin. Max flows in O(nm) time, or better. In 45th STOC, pages 765–774, 2013.DOI
- [23]A. Ramachandra Rao and S. Rao. On factorable degree sequences. Journal of Combinatorial Theory, Series B, 13(3):185–191, 1972.DOI
- [24]A. R. Rao. The clique number of a graph with a given degree sequence. In ISI Lect. Notes, volume 4, pages 251–267, 1979.
- [25]J.-H. Yin. A rao-type characterization for a sequence to have a realization containing a split graph. Discr. Math., 311(21):2485–2489, 2011.
- [26]J.-H. Yin. A short constructive proof of A. R. Rao’s characterization of potentially K_{r+1}-graphic sequences. Discr. Appl. Math., 160(3):352–354, 2012.DOI
