In this paper
AbstractIntroductionPreliminariesThe graphs in ReferencesWorksMathematics
On the Kőnig-Egerváry theorem for -trees
Abstract
The famous Kőnig-Egerváry theorem is equivalent to the statement that a graph is bipartite if and only if the matching number equals the vertex cover number for every induced subgraph. Bessy, Ochem, and Rautenbach (J. Graph Theory 91 (2019) 73-87) generalized this theorem to -paths by introducing the class of graphs where, for every induced subgraph, the maximum number of disjoint paths of order equals the minimum number of vertices intersecting all such paths. They provided complete structural characterizations of graphs in for , and for odd when no cycle of order less than is present. Inspired by this nice work, we extend the Kőnig-Egerváry theorem to -trees (i.e., trees with exactly vertices). We define the class of graphs where, for every induced subgraph, the maximum number of disjoint trees of order equals the minimum number of vertices intersecting all such trees, and provide complete structural descriptions of graphs in for all .
Introduction
An independent edge set in a graph is referred to as a matching. The dual concept of a matching is a vertex cover: a vertex subset such that every edge in is incident to at least one vertex in . For any graph , let denote its matching number (the size of a maximum matching) and its vertex cover number (the size of a minimum vertex cover). A fundamental observation in graph theory is that holds for all graphs. The famous König-Egerváry theorem [6, 11] refines this inequality for bipartite graphs, stating that when is bipartite. Equivalently, this theorem characterizes bipartite graphs as those where every induced subgraph satisfies . This equivalence follows from the fact that odd cycles violate the equality: for such cycles, .
Matching theory can be naturally extended beyond edges to more general subgraph structures through the well-studied packing and covering problems. Given a specified graph class , the packing problem seeks the maximum number of vertex-disjoint subgraphs of that are isomorphic to members of . The dual covering problem aims to find the smallest vertex subset such that every subgraph of isomorphic to a member of intersects .
Note that the classic matching and vertex cover correspond to the special case where , the graph consisting of a single edge. A common generalization focuses on , where is a path with exactly vertices. In this setting: A -matching is a collection of vertex-disjoint -paths in , with the maximum size denoted . A -vertex cover is a vertex set that intersects every -path in , with the minimum size denoted .
Between the two parameters and , only the latter seems to have received considerable attention in the literature [4, 5, 8]. For all integers , the computational hardness of the -vertex cover problem was established by Brešar et al. [4], and the 3-vertex cover number has been studied extensively [9, 10, 13, 14, 16, 18]. Notably, a vertex set of a graph forms a 3-vertex cover if and only if its complement is a so-called dissociation set, a set of vertices inducing a subgraph with maximum degree at most 1. Related problems involving dissociation sets have recently gained significant attention, as demonstrated in [2, 3, 12, 15].
Notably, Tu, Zhang and Shi [15] showed that for every forest and every integer , . Bessy, Ochem and Rautenbach [1] generalized the König-Egerváry theorem to long paths by introducing the graph class , consisting of all graphs such that for every induced subgraph of . They provided complete structural characterizations of graphs in for , and for odd when no cycle of order less than is present.
Since the path is a tree on vertices, the setting can be further generalized to cases where contains all -trees (i.e., trees with exactly vertices for a fixed integer ). Correspondingly, classic graph-theoretic notions of matching and vertex cover extend naturally to their -tree analogs: the generalized -matching and generalized -vertex cover.
A collection of vertex-disjoint -trees in is referred to as a generalized -matching, with the size of a maximum such collection denoted the generalized -matching number .
A generalized -vertex cover is a vertex set that intersects every -tree in , with the
minimum size of such a set termed the generalized -vertex cover number .
It follows directly that holds for any graph . Notably, when , the 3-vertex cover coincides with the generalized 3-vertex cover, and the 3-matching coincides with the generalized 3-matching.
Let denote the class of all graphs such that holds for every induced subgraph of . Then, a natural question arises: how can the König-Egerváry theorem be extended to -trees? In other words, how do we characterize the graphs in ?
In 2024, Li and Xu [7] established that if is a forest, then . This result can be restated as follows:
Theorem 1.1 [7] Every forest belongs to for every integer .
When , we have , so the characterization in [1] applies. In this paper, we provide complete structural characterizations of graphs in for all integers .
Preliminaries
Throughout this paper, graphs are finite, simple and undirected; the auxiliary multigraphs may contain loops and parallel edges. In a multigraph, a loop and a pair of parallel edges count as cycles of lengths one and two, respectively. A -tree means a tree of order , not necessarily an induced subgraph. Let and represent the vertex set and edge set of a graph , respectively. For any graph or vertex set , let denote the cardinality of the underlying vertex set: specifically, and . A connected graph of order at least contains a tree of order . Consequently, a vertex set is a generalized -vertex cover if and only if every component of has fewer than vertices. We use this observation throughout. To provide a comprehensive structural characterization of graphs in for , we first introduce a new concept: the -tree insertion operation.
Let be a graph and let be an edge of . The -tree insertion operation on edge is defined through the following sequential steps:
Remove the edge from .
Introduce a new connected graph with that is disjoint from .
Select two vertices (allowing when ; for a loop, require ).
Connect to by adding edges and .
For an integer , the -tree insertion operation applied to a multigraph , denoted , is obtained by performing the -tree insertion operation on every edge of , using mutually disjoint new graphs. For parallel edges, each subscript refers to the particular edge under consideration. Specifically, when each added graph is a path and the chosen vertices are the two endpoints of this path, the resulting graph is called the -subdivision of , denoted .
The following lemma demonstrates that constructing a graph satisfying can be achieved through straightforward means, a result analogous to the analysis in [1] for graphs containing a block for some multigraph when . Specifically, if where is a connected multigraph containing at least one cycle, then for all . This equality for alone does not assert that .
To formalize the proof of this lemma, we first introduce a standard graph-theoretic concept: A rooted tree is formed by designating a distinguished vertex in a tree as the root. For a rooted tree , the level of a vertex , denoted by , is defined as the distance between and the root of .
Lemma 2.1 Let . Suppose the graph contains an induced subgraph such that for some connected multigraph that contains a cycle. Suppose also that every component of meeting satisfies . Then
(i) ;
(ii) .
Proof. (i) Since is connected and contains a cycle, there exists an edge incident to some vertex such that contains a spanning tree of . Root at . For each with , let be a spanning tree of . Similarly, let be a spanning tree of . Define:
The collection consists of vertex-disjoint -trees. By the additional hypothesis, every component of that contains a vertex from satisfies . Therefore, adding to any generalized -matching of yields a generalized -matching of . It follows that .
Conversely, if is a generalized -matching in , then since every -tree in intersecting contains a vertex of , the set contains at most -trees intersecting . Removing all such -trees from yields a generalized -matching of , which implies that .
By combining the upper and lower bounds established above, we conclude that .
(ii) If is a generalized -vertex cover in , then forms a generalized -vertex cover in . This directly yields the inequality .
For the converse direction, let denote a generalized -vertex cover of . Set . Since meets every tree in , we have . By the component hypothesis, every -tree in is disjoint from . Thus is a generalized -vertex cover of , and
By combining the upper and lower bounds established above, we conclude that .
We next establish a straightforward property of the graph family , which is formalized in the lemma below:
Lemma 2.2 Let and let be a positive integer. Then
(i) Every cycle of length at least in every graph in has length congruent to modulo .
(ii) Let be a cycle of length . A vertex subset is a minimum generalized -vertex cover of if and only if for some .
(iii) Suppose , is a cycle in with , and are distinct vertices of each having at least one neighbor outside . Then .
Proof. Let be a cycle of length in , and let . Then
Every generalized -vertex cover of a cycle must meet every set of consecutive vertices, and selecting vertices with gaps of at most gives a cover of cardinality . Thus
Since is an induced subgraph of , we have , from which part (i) follows.
Statement (ii) follows directly from two key observations: first, the generalized -vertex cover number of the cycle graph satisfies ; second, every generalized -vertex cover of must contain at least one vertex from every set of consecutive vertices on the cycle.
Suppose , cycle , and vertices satisfy the hypotheses of part (iii). By (i), we have . Let be a neighbor of , be a neighbor of , and define as the induced subgraph of with vertex set . Then the generalized -matching number of satisfies:
Since and is an induced subgraph of , we have . Thus,
It follows that every minimum generalized -vertex cover of is also a minimum generalized -vertex cover of . By part (ii), such a set must take the form
for some .
Note that removing from yields disjoint paths each of order , and there is no -tree in . If , its component in , together with , is a connected subgraph of order , a contradiction. Thus , and similarly . Thus, .
Finally, we introduce a classic result on 2-connected graphs: the Ear Decomposition Theorem. This theorem establishes a fundamental characterization of 2-connected graphs through a constructive decomposition, which we now define formally.
An open ear of a graph is a path whose distinct endpoints belong to the graph and whose internal vertices do not. An ear decomposition of is a sequence of edge-disjoint subgraphs whose union is , such that is a cycle and, for each , is an open ear of . Ears of length one are allowed. This structural decomposition provides a powerful framework for characterizing 2-connected graphs, as formalized by the following fundamental theorem:
Theorem 2.3 [17] A graph with at least three vertices is 2-connected if and only if it has an ear decomposition. Furthermore, every cycle in a 2-connected graph can serve as the initial cycle in some ear decomposition of the graph.
The graphs in
In this section, we provide a comprehensive structural characterization of graphs in the family for . Specifically, we explicitly characterize their block structures and formalize constraints governing their cut-vertices. We denote the cut-vertices of contained in by . Let be the component of containing , and let be the union of the vertex sets of all components of disjoint from . Thus unrelated components of are not counted in . The sets are pairwise disjoint. An endblock of is defined as a block containing at most one cut-vertex of . A block is trivial if it is isomorphic to either or .
To formalize our characterization, we first define a new family of graphs that captures these structural properties precisely. Let denote the family of all graphs such that every nontrivial block of satisfies one of the following conditions:
(i) is an endblock on exactly vertices;
(ii) is a block on vertices where , containing cut-vertices of with . Moreover, when , there exists a choice of sets from whose union has fewer than vertices;
(iii) for some multigraph , and every cut-vertex of contained in is a vertex of .
For , the additional requirement in (ii) is equivalently
If satisfies (i) or (ii), there is a vertex such that
Here is the only cut-vertex when there is exactly one, and may be chosen arbitrarily when there is none. The graph is connected, and no edge joins to . Conversely, the existence of such a vertex for a nontrivial block of order at most implies (i) or (ii), since every nonempty contains at least one vertex.
With this definition in place, we can now state our main structural characterization theorem:
Theorem 3.1 For every integer , we have .
Proof. Both classes are closed under disjoint unions, since the parameters are additive over components and the attachment sets are defined within . Thus it suffices to consider connected graphs. First, we show that .
Let be an arbitrary connected graph in . If is a tree, then it follows immediately that . If is not a tree, let denote a nontrivial block of . Since every nontrivial block is 2-connected, we can establish the following general result about 2-connected induced subgraphs of , which will be applied to itself:
Claim 1: If is a 2-connected induced subgraph of , then either or .
Proof of Claim 1: Assume, for contradiction, that . Since , it follows directly from the definition of that . Given , we derive . However, as is 2-connected, the subgraph remains connected for any vertex , and . This implies every generalized -vertex cover of must contain at least two vertices, so . But this contradicts the membership of in , which requires . Thus, our initial assumption is false, and we conclude that either or .
Applying Claim 1 to the nontrivial block (which is a 2-connected induced subgraph of ), we conclude that either or . We then have the following claim about the structure of :
Claim 2: If contains a cycle of length less than , then .
Proof of Claim 2: Suppose, for contradiction, that contains a cycle of length less than and . By Theorem 2.3, choose an ear decomposition of starting with such a cycle. Put . Each is 2-connected, since it contains the 2-connected ear prefix as a spanning subgraph. Choose the first with . Claim 1 gives
Hence the ear , with endpoints , has length at least .
Choose a shortest – path in . Its length satisfies , and is a cycle with . Since is induced and has minimum degree at least two, each endpoint of has a neighbor in , hence outside . Lemma 2.2(iii) implies that is a multiple of , a contradiction.
With the constraint on the size of such blocks established, we now characterize their structural properties relative to the family :
Claim 3: Let be a nontrivial block of with . Then
(a) If , then satisfies condition (i) in the definition of .
(b) If , then satisfies condition (ii) in the definition of .
Proof of Claim 3: (a) Suppose, for contradiction, that is not an endblock of . Then contains at least two cut-vertices of , denoted by and . Since , there exists a vertex . As is 2-connected, both and are connected. Let and be neighbors of and outside , respectively, and consider the induced subgraph . Since and is an induced subgraph of , it follows that . Note that for all , so . However, removing any single vertex from leaves a connected subgraph of order at least , which implies . This contradicts the definition of , which requires . Therefore, our initial assumption is false, and must be an endblock of .
(b) Similarly, suppose, for contradiction, that contains at least cut-vertices of . Let be cut-vertices of contained in , and let be a neighbor of outside for each . Let be the induced subgraph . Then , so for all . It follows that . However, removing any single vertex from leaves a connected subgraph of order at least , which implies . Since is an induced subgraph of and , we have , which requires . This contradiction establishes that has at most cut-vertices in $G.
Moreover, suppose contains cut-vertices where . Let and . For contradiction, assume that condition (1) fails. Then
Replacing each by preserves these inequalities. Choose integers satisfying for every , with as small as possible. If , the constraints are equivalent to . If , decreasing any positive by one preserves the constraints, a contradiction. Consequently,
For each , choose with such that is connected. This is possible because is connected. Let
The graph is connected and
since (see Figure 1). Removing leaves the connected graph formed by and all with , whose order is at least . Removing a vertex of other than the leaves a connected graph of at least vertices. Finally, if a vertex of is removed, then together with all for remains connected and has at least vertices. Thus , whereas . This contradicts and proves condition (ii).

Figure 1. Cut-vertices of block and the selected parts of their attachments.
We now consider the remaining case . By Claim 2, every cycle in has length at least , and Lemma 2.2(i) implies that every such length is a multiple of . Every cycle in is chordless. Indeed, a chord would divide a cycle into two cycles whose lengths sum to the original length plus two; all three lengths would be divisible by , implying , a contradiction.
If itself is a cycle, Lemma 2.2(iii) implies that all its vertices having neighbors outside occur in one residue class of positions modulo . Choosing every th vertex in this class as an original vertex (or choosing any class if there are no such vertices) gives with all cut-vertices of in among the vertices of .
Otherwise, split the edges of into maximal paths whose endpoints have degree at least 3 in and whose internal vertices have degree 2 in . Each such path lies on a cycle of . Since is chordless, both and have neighbors outside . By Lemma 2.2(iii), together with (i), the length of is a multiple of .
We now define a multigraph by replacing every such path by the path of length . It is clear that , and every cut-vertex of contained in is a vertex of . Thus , and we conclude that .
Next, we establish the inclusion .
First, we verify that is hereditary. Let be an induced subgraph of , and let be a nontrivial block of . The block is contained in a unique block of . If satisfies (i) or (ii), choose and as in (2). If the component of containing does not contain , that component lies in and has fewer than vertices, so satisfies (ii). Otherwise, choose if ; if , let be the unique vertex of through which the component of containing attaches to . Uniqueness follows from the maximality of the block . Every vertex outside can be reached from only through , hence through . Thus together with all its attachments in away from is contained in and has order at most . By the equivalence described after (2), satisfies (i) or (ii).
If satisfies (iii), every internal vertex of a subdivision path has degree in . If contains one such vertex, its degree in the -connected graph is at least , so both neighbors and both incident edges lie in . Continuing along the path shows that the entire subdivision path belongs to . Consequently, is the -subdivision of a connected submultigraph of containing a cycle. A cut-vertex of in has degree at least in , so it cannot be an internal subdivision vertex. Therefore satisfies (iii), proving the hereditary property.
It now suffices to show that for every connected graph , which we prove by induction on the sum of the order and size of . If is a tree, Theorem 1.1 immediately implies . If is a cycle of length less than , both parameters are zero. If its length is a multiple of , then holds as well. These are the only cycle lengths permitted by the definition of . We may therefore assume that is neither a tree nor a cycle.
Suppose that contains a block satisfying condition (i). Then and . By the hereditary property established above, . Applying the induction hypothesis, we have . Combining these equalities yields .
Suppose contains a block satisfying condition (ii). Choose and as in (2), and let be obtained by replacing by a spanning tree on the same vertex set. The graph remains connected, and has fewer edges than . We show that and .
In both graphs, every -tree meeting contains , since and this set has no neighbors outside . Hence at most one member of a generalized -matching meets . If a -tree in such a matching meets , remove its vertices in . The remaining tree is connected and contains : no path in can enter and leave without passing through twice. In the other graph, grow a tree from inside using the same number of additional vertices, and join it to the remaining part of . This gives a -tree disjoint from all other members of the matching. Applying this argument in both directions proves .
If a generalized -vertex cover of meets , then covers and has cardinality at most . If is disjoint from , replacing the connected graph on by another connected graph on the same vertex set leaves the vertex sets of the components after deleting unchanged. Thus also covers . The same argument with and interchanged proves .
The nontrivial blocks of are precisely the nontrivial blocks of other than . Their attachment sets are unchanged, since the replacement preserves connectivity between all vertices of ; at a cut-vertex shared with another block, the vertices on the side remain on that side. Thus . By induction, , and consequently .
In all such cases, the induction hypothesis yields . We may therefore assume that contains no such blocks. Let for some multigraph , where every cut-vertex of contained in is a vertex of . The multigraph is connected and contains a cycle. Every internal subdivision vertex has degree 2 in , so each component of meeting is an internal subdivision path of order . Thus the additional hypothesis of Lemma 2.1 holds. Applying that lemma to , we obtain and . Since is hereditary, the induction hypothesis gives , which implies . Since is hereditary, the same equality holds for every induced subgraph of , proving and completing the proof.
References
- [1]S. Bessy, P. Ochem, D. Rautenbach, On the König-Egerváry theorem for k-paths, J. Graph Theory, 91 (2019) 73-87.DOI
- [2]F. Bock, J. Pardey, L. Penso, D. Rautenbach, A bound on the dissociation number, J. Graph Theory, 103(4)(2023) 661-673.arxiv.org/abs/2202.09190
- [3]F. Bock, J. Pardey, L. Penso, D. Rautenbach, Relating the independence number and the dissociation number, J. Graph Theory, 104(2023) 320-340.arxiv.org/abs/2205.03404
- [4]B. Brešar, F. Kardoš, J. Katrenič, G. Semanišin, Minimum k-path vertex cover, Discrete Appl. Math., 159 (2011) 1189-1195.DOI
- [5]B. Brešar, M. Jakovac, J. Katrenič, G. Semanišin, A. Taranenko, On the vertex k-path cover, Discrete Appl. Math., 161 (2013)1943-1949.
- [6]E. Egerváry, Über kombinatorische Eigenschaften von Matrizen, Mat. Fiz. Lapok, 38 (1931) 16-28.
- [7]P. Li, M. Xu, The maximum number of maximum generalized 4-independent sets in trees, J. Graph Theory, 107 (2024) 359-380.DOI
- [8]X. Li, Z. Zhang and X. Huang, Approximation algorithms for minimum (weight) connected k-path vertex cover, Discrete Appl. Math., 205 (2016) 101-108.DOI
- [9]F. Kardoš, J. Katrenič and I. Schiermeyer, On computing the minimum 3-path vertex cover and dissociation number of graphs, Theoret. Comput. Sci., 412 (2011) 7009-7017.DOI
- [10]J. Katrenič, A faster FPT algorithm for 3-path vertex cover, Inform. Process. Lett., 116 (2016) 273-278.DOI
- [11]D. König, Graphen und Matrizen, Mat. Fiz. Lapok., 38 (1931) 116-119.
- [12]W. Sun, S. Li, On the maximal number of maximum dissociation sets in forests with fixed order and dissociation number, Taiwanese J. Math., 27 (4)(2023)647-683.DOI
- [13]J. Tu, L. Wu, J. Yuan, L. Cui, On the vertex cover P₃ problem parameterized by treewidth, J. Comb. Optim., 34 (2017) 414-425.DOI
- [14]J. Tu and W. Zhou, A primal-dual approximation algorithm for the vertex cover P₃ problem, Theor. Comput. Sci., 412 (2011)7044-7048.DOI
- [15]J. Tu, Z. Zhang, Y. Shi, The maximum number of maximum dissociation sets in trees, J. Graph Theory, 96(4) (2021) 472-489.
- [16]J. Tu, A survey on the k-path vertex cover problem, Axioms, 2022, 11, 191. https://doi.org/10.3390/axioms11050191.
- [17]H. Whitney, Congruent graphs and the connectivity of graphs, Amer. J. Math., 54 (1932) 150-168.
- [18]M. Xiao and S. Kou, Exact algorithms for the maximum dissociation set and minimum 3-path vertex cover problems, Theor. Comput. Sci., 657 (2017) 86-97.DOI