It is shown that for any 4-regular graph G there is a collection ƒ of paths of length 4-such that each edge of G belongs to exactly two of the paths and each vertex of G occurs exactly twice as an endvertex of a path of ƒ This proves a special case of a conlecture of Bondy

Let G be a graph with vertex set V(G). Let n; k and d be non-negative integers such that n+2k+d6|V(G)|−2 and |V(G)|−n−d is even. A matching which covers exactly |V(G)|−d vertices of G is called a defect-d matching of G. If when deleting any n vertices of G the remaining subgraph contains a matching of k edges and every k-matching can be extended o a defect-d matching, then G is called a (n; k; d)-graph. In this paper a characterization of (n; k; d)-graphs is given and several properties (such as connectivity, minimum degree, hierarchy, etc.) of (n; k; d)-graphs are investigated.

Let n be a non-negative integer. A graph G is said to be n-factor-critical if the subgraph G-S has a perfect matching for any subset S of V(G) with jSj=n. In this paper, we provide much shorter proofs of two main theorems about extendability and factor-criticality obtained by Favaron [2]. Furthermore, we present a solution to an open problem posted in the same paper.

A graph G is k-extendable if it contains a set of k independent edges and each set of k independent edges can be extended to a perfect matching of G. In this note, we present degree-sum conditions for graphs to be k-extendable.

Let G be a graph of order n≥4k+1, where k is a positive integer with kn even and δ(G)≥k. We prove that if the degree sum of each pair of nonadjacent ertices is at least n+1, then G has a k-factor including any given edge. Similarly, a sufficient condition for graphs to have a k-factor excluding any given edge is also given.