# Graphs Whose Edge Set Can Be Partitioned into  Maximum Matchings

Authors: Niraj Khare
Journal: ISRN Combinatorics
 (2013)

---

## Abstract

This paper provides structural characterization of simple graphs whose edge set can be partitioned into maximum matchings. We use Vizing's classification of simple graphs based on edge chromatic index.


---

## Body

## 1. Introduction

By a simple graph, we shall mean a graph with no loop and no multiple edges. We will only consider simple graphs withno isolated vertex. We first fix some notations. For a graph G, E(G), and V(G) would denote the edge set and the vertex set of G, respectively. Δ(G), ν(G), and χ′(G) would denote the maximum degree of any vertex in G, the size of a maximum matching in G and the edge chromatic index of G, respectively. For x∈V(G), degG(x) would denote the degree of the vertex x and G∖x would denote the induced subgraph on V(G)∖{x}.We now consider simple graphs whose edge set can be partitioned into maximum matchings. Complete graphs and even cycles are some of the examples but there are numerous other examples too. For instance, consider the graph in Figure1.Figure 1
A graph whose edge set can be partitioned into maximum matchings.Vizing’s celebrated theorem states thatχ′(G)≤Δ(G)+1 for a simple graph G. The definition of the edge chromatic index implies that χ′(G)≥Δ(G). Therefore Vizing classified simple graphs as follows: a simple graph G is in class I if and only if χ′(G)=Δ(G) and a simple graph G is in class II if and only if χ′(G)=Δ(G)+1. There is no structural characterization yet known for the graphs in class I or in class II. It is NP-complete to determine whether a simple graph is in Class I or Class II (see [1]). But under certain restrictions structural characterization of class I and class II graphs has been achieved. It is also known that all planar graphs with maximum degree at least seven are in Class I (see [2, 3]). Another interesting result concerns itself with relative cardinality of Class I and Class II (see [4]). We will characterize Class I and class II graphs whose edge set can be partitioned into maximum matchings.


## 2. Results

Our main aim in this paper is to prove the following results.Theorem 1.
LetG be a simple graph such that ν(G)≥2, Δ(G)≥2, and |E(G)|=Δ(G)ν(G)+⌊ν(G)/⌈Δ(G)/2⌉⌋⌊Δ(G)/2⌋. G is a unique graph up to isomorphism if and only if ⌈Δ(G)/2⌉ divides ν(G).Theorem 2.
IfG is a Class II graph and E(G) has a partition into maximum matchings, then Δ(G) is even and G is the graph with exactly 2ν(G)/Δ(G) components each isomorphic to KΔ(G)+1, the complete graph of order Δ(G)+1.Theorem 3.
IfG is a Class I graph and E(G) can be partitioned into maximum matchings, then E(G) has a partition into subgraphs that are either K1,Δ(G) or a factor critical graph H such that E(H) can also be partitioned into maximum matchings and χ′(H)=χ′(G).


## 3. Preliminaries

We first establish some basic results that will be extremely useful in the next section. We will be borrowing some ideas and results discussed in [5]. The following definition is in [5].Definition 4.
Letd, m be positive integers and G be a simple graph with Δ(G)<d and ν(G)<m.  G∈ℱ(d,m) if and only if for any simple graph G′ such that |E(G′)|>|E(G)| and G is a subgraph of  G′, either Δ(G′)≥d or ν(G′)≥m.Theorem 5.
For a simple graphG, if ν:=ν(G) and Δ:=Δ(G), then
(1)|E(G)|≤Δν+⌊ν⌈Δ/2⌉⌋⌊Δ2⌋(2)|E(G)|≤ν(Δ+⌊Δ/2⌋⌈Δ/2⌉).Proof.
It is obvious that for each graphG with Δ(G)=Δ and ν(G)=ν there exists a maximal graph G′ such that ν(G′)=ν, Δ(G′)=Δ, |E(G′)|≥|E(G)| and G′∈ℱ(Δ+1,ν+1). Note that a maximal graph such as G′ can be constructed by adding edges or new vertices and edges to G. The upper bound for |E(H)| obtained in [5] implies that for any H∈ℱ(d,m), |E(H)|≤(d-1)(m-1)+⌊(m-1)/⌈(d-1)/2⌉⌋⌊(d-1)/2⌋. Therefore,
(3)|E(G′)|≤Δν+⌊ν⌈Δ/2⌉⌋⌊Δ2⌋≤ν(Δ+⌊Δ/2⌋⌈Δ/2⌉).Note that the above bound can also be inferred from [6]. However, the method used in [6] is more involved and it does not help in ascertaining uniqueness of the graphs achieving the edge bound (1) for given Δ and ν values, that is, Theorem 1. Our first goal is to prove Theorem 1. We next define a factor-critical graph and state the Gallai’s lemma that is crucial to the following discussion. An elegant proof of the Gallai’s lemma can be found in [7].Definition 6.
A simple, connected graphG is called factor-critical if and only if G∖x has a perfect matching for all x∈V(G).Lemma 77 (Gallai).
LetG be a simple, connected graph. If  ν(G∖x)=ν(G) for all x∈V(G), then G is a factor-critical graph.We will consider graphs withno isolated vertex only. Now we consider those graphs that attain the edge bound and analyze under what conditions these graphs are unique. We first consider some trivial cases.Remark 8.
ForΔ=1, the graph that attains the edge bound (1) consists of ν components where each component is K2. For ν=1 and Δ>3, the unique graph that attains the edge bound (1) is K1,Δ. For ν=1 and Δ=2 the unique graph that attains the edge bound is K3. But there are two graphs G that satisfy Δ(G)≤3, ν(G)=1 and attain the edge bound |E(G)|=3. These graphs are K3 and K1,3.We next consider all cases involvingΔ≥2 and ν≥2.


### 3.1. Unique Graph𝒞

LetΔ≥2 be a positive integer. We consider simple graphs G with no isolated vertex such that
(4)ν(G)=⌈Δ2⌉,Δ(G)=Δ,|E(G)|=⌊(2(⌈Δ/2⌉)+1)(Δ)2⌋=(Δ+⌊Δ/2⌋⌈Δ/2⌉)⌈Δ2⌉.
Note that the last equation ensures that |E(G)| attains the maximum edge bound given by (1). We will now construct a graph 𝒞 satisfying (4) as follows.Case (I). Let Δ be an even integer. In this case, let 𝒞=KΔ+1.Case (II). Let Δ=2j-1 for some j≥2. In this case, let ℰ be the graph obtained from K2j by removing a maximum matching. To obtain 𝒞, we connect any 2j-1 of the vertices of ℰ to a new vertex, v∉V(ℰ).We next prove that𝒞 is the unique graph satisfying (4).Proposition 9.
LetΔ≥2 and 𝒞 be the simple graph described above. If G is a simple graph satisfying (4) then(a)
ν(G∖x)=ν(G)for allx∈V(G),(b)
Gis connected,(c)
G≃𝒞.Proof.
LetG be a graph satisfying the conditions of the proposition.Proof of (a).
If the statement (a) is false then there exists a vertexx∈V(G) such that ν(G∖x)<ν(G). As at most one edge can cover x in any maximum matching, we have ν(G∖x)=ν(G)-1. Therefore,
(5)|E(G)|≤|E(G∖x)|+Δ(G∖x)≤(Δ(G∖x)+⌊Δ(G∖x)/2⌋⌈Δ(G∖x)/2⌉)ν(G∖x)+Δ(G∖x)[by(2)]
The above expression is a nondecreasing function of Δ(G∖x) for a fixed ν(G∖x). Since Δ≥Δ(G∖x), we have
(6)|E(G)|≤(Δ+⌊Δ/2⌋⌈Δ/2⌉)ν(G∖x)+Δ=(Δ+⌊Δ/2⌋⌈Δ/2⌉)(ν-1)+Δ=(Δ+⌊Δ/2⌋⌈Δ/2⌉)ν-⌊Δ/2⌋⌈Δ/2⌉.
Therefore by assumption and the above equation, we have |E(G)|≤|E(G)|-⌊Δ/2⌋/⌈Δ/2⌉. But 0<⌊Δ/2⌋/⌈Δ/2⌉, since Δ≥2. Hence the statement (a) holds.Proof of (b).
On the contrary assume thatG is not connected. Let 𝒞1 be a component of G. Then 1≤ν(𝒞1)<ν(G)=⌈Δ/2⌉ as G has no isolated vertex and G is not connected by assumption. By statement (a) and Gallai’s Lemma (Lemma 7), 𝒞1 is a factor-critical component. Therefore, |V(𝒞1)|=2ν(𝒞1)+1. So,
(7)|E(𝒞1)|≤(2ν(𝒞1)+1)Δ(𝒞1)2≤(2ν(𝒞1)+1)ν(𝒞1).
The above inequality implies that(8)|E(𝒞1)|ν(𝒞1)≤2ν(𝒞1)+1≤2(⌈Δ2⌉-1)+1<Δ+⌊Δ/2⌋⌈Δ/2⌉[asforΔ≥2,2(⌈Δ2⌉-Δ2)-1≤0<⌊Δ/2⌋⌈Δ/2⌉].
So there is a component 𝒞2 of G such that (|E(𝒞2)|/ν(𝒞2))>Δ+(⌊Δ/2⌋/⌈Δ/2⌉) as (|E(G)|/ν(G))=Δ+(⌊Δ/2⌋/⌈Δ/2⌉). But the (2) demands that (|E(𝒞2)|/ν(𝒞2))≤Δ+(⌊Δ/2⌋/⌈Δ/2⌉). The contradiction implies that the statement (b) holds.Proof of (c).
Since the statements(a) and (b) hold for G, G is factor-critical by Gallai’s Lemma (Lemma 7). As ν(G)=⌈Δ/2⌉, we have |V(G)|=2(⌈Δ/2⌉)+1. We consider following two cases.
IfΔ is even then G is a connected graph with 2(⌈Δ/2⌉)+1=Δ+1 vertices and |E(G)|=(Δ+(⌊Δ/2⌋/⌈Δ/2⌉))⌈Δ/2⌉=((Δ+1)Δ/2). Therefore, degG(x)=Δ for all x∈V(G). Hence G is KΔ+1, the complete graph on Δ+1 vertices. So G≃𝒞.
IfΔ is odd. Let Δ=2j-1 for some j≥2. Then ν(G)=⌈Δ/2⌉=j, |V(G)|=2ν(G)+1=2j+1 and |E(G)|=(Δ+(⌊Δ/2⌋/⌈Δ/2⌉))⌈Δ/2⌉=(2j-1)j+j-1. So
(9)∑x∈V(G)degG(x)=2j(2j-1)+2j-2.Therefore there is a unique vertexv∈V(G) of degree 2j-2. Hence there is a vertex u in V(G) which is not a neighbor of v. Consequently G∖u is a regular graph of degree 2j-2 on 2j vertices and hence its complement is a regular graph of degree one, namely, a matching of a complete graph on 2j vertices. This establishes G≃𝒞, where 𝒞 is the graph described earlier for the case Δ=2j-1.


### 3.2. Unique Graphs with Maximum Number of Edges for a Given Maximum Degree and Matching Size

We emphasize that graphs considered in this discussion have no isolated vertex. Note that a method is provided in [5] to construct a graph G such that |E(G)| attains the edge bound given by (1). We find the condition when the graphs that attain the maximum edge bound (1) are unique up to isomorphism.Proposition 10.
Let𝒞 be the graph constructed in the Section 3.1 and G be a simple graph with ν:=ν(G) and Δ:=Δ(G) such that Δ≥2. If ⌈Δ/2⌉ divides ν and |E(G)|=Δν+(ν⌊Δ/2⌋/⌈Δ/2⌉), then (a)
ν(G∖x)=ν(G)for allx∈V(G),(b)
ifDis a component ofGwithν(D)>ν(𝒞), then(|E(D)|/ν(D))<(|E(𝒞)|/ν(𝒞)),(c)
ifDis a component ofGwithν(D)<ν(𝒞), then(|E(D)|/ν(D))<(|E(𝒞)|/ν(𝒞)),(d)
every component ofGis isomorphic to𝒞,(e)
Gis unique up to isomorphism.Proof.
LetG be a graph satisfying the conditions of the proposition.Proof of (a).
If the statement (a) is false then there exists a vertexv∈V(G) such that ν(G∖v)<ν(G). This implies
(10)Δν+ν⌈Δ/2⌉⌊Δ2⌋=|E(G)|≤degG(v)+|E(G∖v)|≤Δ+Δ(G∖v)(ν-1)+⌊ν-1⌈Δ(G∖v)/2⌉⌋⌊Δ(G∖v)2⌋.
We again note that the edge bound, that is, (1) is a nondecreasing function of Δ for a fixed ν. Also Δ≥Δ(G∖v). Therefore,
(11)⇒ν⌈Δ/2⌉⌊Δ2⌋≤⌊ν-1⌈Δ/2⌉⌋⌊Δ2⌋≤(ν-1)⌈Δ/2⌉⌊Δ2⌋⇒ν≤ν-1.
This contradiction proves (a).We recall that the graph𝒞 is a factor critical graph with Δ⌈Δ/2⌉+⌊Δ/2⌋ edges and maximum matching size ⌈Δ/2⌉.Proof of (b).
LetD be a component of G. Gallai’s lemma and (a) imply that D is factor-critical, hence |V(D)|=2ν(D)+1 and
(12)|E(D)|≤⌊(2ν(D)+1)Δ2⌋=ν(D)Δ+⌊Δ2⌋.
Note that in the following inequality we again used the fact that the edge bound, that is, (1) is a nondecreasing function of Δ for a fixed ν. If ν(D)>ν(𝒞), then
(13)|E(D)|ν(D)≤Δ+⌊Δ/2⌋ν(D)<Δ+⌊Δ/2⌋ν(𝒞)=Δ+⌊Δ/2⌋⌈Δ/2⌉=|E(𝒞)|ν(𝒞).
This proves (b).Proof of (c).
LetD be a component of G. By Gallai’s lemma and (a), D is a factor-critical graph and hence |V(D)|=2ν(D)+1. Thus
(14)|E(D)|≤(2ν(D)+1)2ν(D)2=(2ν(D)+1)ν(D).
Now sinceν(D)≤ν(𝒞)-1, we have
(15)|E(D)|ν(D)≤2ν(D)+1≤2ν(𝒞)-1=2⌈Δ2⌉-1<Δ+⌊Δ/2⌋⌈Δ/2⌉=|E(𝒞)|ν(𝒞),
which proves (c).Proof of (d).
From (b) and (c), every componentD of G has ν(D)=ν(𝒞)=⌈Δ/2⌉ and also |E(D)|=Δ⌈Δ/2⌉+⌊Δ/2⌋. Since 𝒞 is the only graph with maximum matching size ⌈Δ/2⌉ and the number of edges Δ⌈Δ/2⌉+⌊Δ/2⌋, D must be isomorphic to 𝒞. This proves (d).Proof of (e).
This follows from (d).Now we explore the inverse of Proposition10. Recall the connected graph 𝒞 described in Section 3.1 is the unique graph satisfying (4).Proposition 11.
LetG1 be a simple graph such that |E(G1)|=Δ(G1)ν(G1)+⌊ν(G1)/⌈Δ(G1)/2⌉⌋⌊Δ(G1)/2⌋, that is, G1 attains the maximum edge bound given by the inequality (1). If ν(G1)≥2, Δ(G1)≥2 and ⌈Δ(G1)/2⌉ does not divide ν(G1), then there exists a simple graph G2 such that |E(G2)|=|E(G1)|, ν(G2)=ν(G1), Δ(G2)=Δ(G1) and G2 is not  isomorphic to G1.Proof.
We use the method given in [5] to construct a simple graph G such that |E(G)|=|E(G1)|, ν(G)=ν(G1), and Δ(G)=Δ(G1). Let G have t:=ν(G1)-(⌈Δ(G1)/2⌉)⌊ν(G1)/⌈Δ(G1)/2⌉⌋ components isomorphic to K1,Δ(G1) and ⌊ν(G1)/⌈Δ(G1)/2⌉⌋ components isomorphic to 𝒞 (described in Section 3.1). Let G2=G if G1 is not isomorphic to G. So assume that G1 is isomorphic to G. Note that t:=ν(G1)-(⌈Δ(G1)/2⌉)⌊ν(G1)/⌈Δ(G1)/2⌉⌋≥1 as ⌈Δ(G1)/2⌉ does not divide ν(G1). If t≥2 then let H1 and H2 be two components of G1 isomorphic to K1,Δ(G1). We remove an edge of H1 and then connect the vertex of degree Δ(G1)-1 of H1 to any vertex of degree one in H2 by a new edge. Thus, a new graph G2 is obtained. It is obvious by construction that G2 satisfies hypothesis of Proposition 11. So, we need to consider only the case t=1 to complete the proof. As ν(G1)≥2 and t=1, G1 has at least two components. Hence G1 has a component isomorphic to K1,Δ(G1) and at least one component isomorphic to 𝒞. As Δ(G1)+|E(𝒞)|=Δ(G1)+Δ(G1)(⌈Δ(G1)/2⌉)+⌊Δ(G1)/2⌋≤⌊(2(⌈Δ(G1)/2⌉+1)+1)Δ(G1)/2⌋, we can coalesce the two components to form a factor-critical component with 2(⌈Δ(G1)/2⌉+1)+1 vertices and maximum degree at most Δ(G1) which has number of edges equal to Δ(G1)+|E(𝒞)| and maximum matching size equal to ν(𝒞)+1. Thus, again a new graph G2 is obtained. It is obvious by construction that G2 satisfies hypothesis of Proposition 11.We can combine the above two propositions in the following theorem.Theorem 12.
LetG be a simple graph such that ν(G)≥2, Δ(G)≥2 and |E(G)|=Δ(G)ν(G)+⌊ν(G)/⌈Δ(G)/2⌉⌋⌊Δ(G)/2⌋. G is a unique graph up to isomorphism if and only if ⌈Δ(G)/2⌉ divides ν(G).Proof.
The above conclusion follows by Propositions10 and 11.


## 3.1. Unique Graph𝒞

LetΔ≥2 be a positive integer. We consider simple graphs G with no isolated vertex such that
(4)ν(G)=⌈Δ2⌉,Δ(G)=Δ,|E(G)|=⌊(2(⌈Δ/2⌉)+1)(Δ)2⌋=(Δ+⌊Δ/2⌋⌈Δ/2⌉)⌈Δ2⌉.
Note that the last equation ensures that |E(G)| attains the maximum edge bound given by (1). We will now construct a graph 𝒞 satisfying (4) as follows.Case (I). Let Δ be an even integer. In this case, let 𝒞=KΔ+1.Case (II). Let Δ=2j-1 for some j≥2. In this case, let ℰ be the graph obtained from K2j by removing a maximum matching. To obtain 𝒞, we connect any 2j-1 of the vertices of ℰ to a new vertex, v∉V(ℰ).We next prove that𝒞 is the unique graph satisfying (4).Proposition 9.
LetΔ≥2 and 𝒞 be the simple graph described above. If G is a simple graph satisfying (4) then(a)
ν(G∖x)=ν(G)for allx∈V(G),(b)
Gis connected,(c)
G≃𝒞.Proof.
LetG be a graph satisfying the conditions of the proposition.Proof of (a).
If the statement (a) is false then there exists a vertexx∈V(G) such that ν(G∖x)<ν(G). As at most one edge can cover x in any maximum matching, we have ν(G∖x)=ν(G)-1. Therefore,
(5)|E(G)|≤|E(G∖x)|+Δ(G∖x)≤(Δ(G∖x)+⌊Δ(G∖x)/2⌋⌈Δ(G∖x)/2⌉)ν(G∖x)+Δ(G∖x)[by(2)]
The above expression is a nondecreasing function of Δ(G∖x) for a fixed ν(G∖x). Since Δ≥Δ(G∖x), we have
(6)|E(G)|≤(Δ+⌊Δ/2⌋⌈Δ/2⌉)ν(G∖x)+Δ=(Δ+⌊Δ/2⌋⌈Δ/2⌉)(ν-1)+Δ=(Δ+⌊Δ/2⌋⌈Δ/2⌉)ν-⌊Δ/2⌋⌈Δ/2⌉.
Therefore by assumption and the above equation, we have |E(G)|≤|E(G)|-⌊Δ/2⌋/⌈Δ/2⌉. But 0<⌊Δ/2⌋/⌈Δ/2⌉, since Δ≥2. Hence the statement (a) holds.Proof of (b).
On the contrary assume thatG is not connected. Let 𝒞1 be a component of G. Then 1≤ν(𝒞1)<ν(G)=⌈Δ/2⌉ as G has no isolated vertex and G is not connected by assumption. By statement (a) and Gallai’s Lemma (Lemma 7), 𝒞1 is a factor-critical component. Therefore, |V(𝒞1)|=2ν(𝒞1)+1. So,
(7)|E(𝒞1)|≤(2ν(𝒞1)+1)Δ(𝒞1)2≤(2ν(𝒞1)+1)ν(𝒞1).
The above inequality implies that(8)|E(𝒞1)|ν(𝒞1)≤2ν(𝒞1)+1≤2(⌈Δ2⌉-1)+1<Δ+⌊Δ/2⌋⌈Δ/2⌉[asforΔ≥2,2(⌈Δ2⌉-Δ2)-1≤0<⌊Δ/2⌋⌈Δ/2⌉].
So there is a component 𝒞2 of G such that (|E(𝒞2)|/ν(𝒞2))>Δ+(⌊Δ/2⌋/⌈Δ/2⌉) as (|E(G)|/ν(G))=Δ+(⌊Δ/2⌋/⌈Δ/2⌉). But the (2) demands that (|E(𝒞2)|/ν(𝒞2))≤Δ+(⌊Δ/2⌋/⌈Δ/2⌉). The contradiction implies that the statement (b) holds.Proof of (c).
Since the statements(a) and (b) hold for G, G is factor-critical by Gallai’s Lemma (Lemma 7). As ν(G)=⌈Δ/2⌉, we have |V(G)|=2(⌈Δ/2⌉)+1. We consider following two cases.
IfΔ is even then G is a connected graph with 2(⌈Δ/2⌉)+1=Δ+1 vertices and |E(G)|=(Δ+(⌊Δ/2⌋/⌈Δ/2⌉))⌈Δ/2⌉=((Δ+1)Δ/2). Therefore, degG(x)=Δ for all x∈V(G). Hence G is KΔ+1, the complete graph on Δ+1 vertices. So G≃𝒞.
IfΔ is odd. Let Δ=2j-1 for some j≥2. Then ν(G)=⌈Δ/2⌉=j, |V(G)|=2ν(G)+1=2j+1 and |E(G)|=(Δ+(⌊Δ/2⌋/⌈Δ/2⌉))⌈Δ/2⌉=(2j-1)j+j-1. So
(9)∑x∈V(G)degG(x)=2j(2j-1)+2j-2.Therefore there is a unique vertexv∈V(G) of degree 2j-2. Hence there is a vertex u in V(G) which is not a neighbor of v. Consequently G∖u is a regular graph of degree 2j-2 on 2j vertices and hence its complement is a regular graph of degree one, namely, a matching of a complete graph on 2j vertices. This establishes G≃𝒞, where 𝒞 is the graph described earlier for the case Δ=2j-1.


## 3.2. Unique Graphs with Maximum Number of Edges for a Given Maximum Degree and Matching Size

We emphasize that graphs considered in this discussion have no isolated vertex. Note that a method is provided in [5] to construct a graph G such that |E(G)| attains the edge bound given by (1). We find the condition when the graphs that attain the maximum edge bound (1) are unique up to isomorphism.Proposition 10.
Let𝒞 be the graph constructed in the Section 3.1 and G be a simple graph with ν:=ν(G) and Δ:=Δ(G) such that Δ≥2. If ⌈Δ/2⌉ divides ν and |E(G)|=Δν+(ν⌊Δ/2⌋/⌈Δ/2⌉), then (a)
ν(G∖x)=ν(G)for allx∈V(G),(b)
ifDis a component ofGwithν(D)>ν(𝒞), then(|E(D)|/ν(D))<(|E(𝒞)|/ν(𝒞)),(c)
ifDis a component ofGwithν(D)<ν(𝒞), then(|E(D)|/ν(D))<(|E(𝒞)|/ν(𝒞)),(d)
every component ofGis isomorphic to𝒞,(e)
Gis unique up to isomorphism.Proof.
LetG be a graph satisfying the conditions of the proposition.Proof of (a).
If the statement (a) is false then there exists a vertexv∈V(G) such that ν(G∖v)<ν(G). This implies
(10)Δν+ν⌈Δ/2⌉⌊Δ2⌋=|E(G)|≤degG(v)+|E(G∖v)|≤Δ+Δ(G∖v)(ν-1)+⌊ν-1⌈Δ(G∖v)/2⌉⌋⌊Δ(G∖v)2⌋.
We again note that the edge bound, that is, (1) is a nondecreasing function of Δ for a fixed ν. Also Δ≥Δ(G∖v). Therefore,
(11)⇒ν⌈Δ/2⌉⌊Δ2⌋≤⌊ν-1⌈Δ/2⌉⌋⌊Δ2⌋≤(ν-1)⌈Δ/2⌉⌊Δ2⌋⇒ν≤ν-1.
This contradiction proves (a).We recall that the graph𝒞 is a factor critical graph with Δ⌈Δ/2⌉+⌊Δ/2⌋ edges and maximum matching size ⌈Δ/2⌉.Proof of (b).
LetD be a component of G. Gallai’s lemma and (a) imply that D is factor-critical, hence |V(D)|=2ν(D)+1 and
(12)|E(D)|≤⌊(2ν(D)+1)Δ2⌋=ν(D)Δ+⌊Δ2⌋.
Note that in the following inequality we again used the fact that the edge bound, that is, (1) is a nondecreasing function of Δ for a fixed ν. If ν(D)>ν(𝒞), then
(13)|E(D)|ν(D)≤Δ+⌊Δ/2⌋ν(D)<Δ+⌊Δ/2⌋ν(𝒞)=Δ+⌊Δ/2⌋⌈Δ/2⌉=|E(𝒞)|ν(𝒞).
This proves (b).Proof of (c).
LetD be a component of G. By Gallai’s lemma and (a), D is a factor-critical graph and hence |V(D)|=2ν(D)+1. Thus
(14)|E(D)|≤(2ν(D)+1)2ν(D)2=(2ν(D)+1)ν(D).
Now sinceν(D)≤ν(𝒞)-1, we have
(15)|E(D)|ν(D)≤2ν(D)+1≤2ν(𝒞)-1=2⌈Δ2⌉-1<Δ+⌊Δ/2⌋⌈Δ/2⌉=|E(𝒞)|ν(𝒞),
which proves (c).Proof of (d).
From (b) and (c), every componentD of G has ν(D)=ν(𝒞)=⌈Δ/2⌉ and also |E(D)|=Δ⌈Δ/2⌉+⌊Δ/2⌋. Since 𝒞 is the only graph with maximum matching size ⌈Δ/2⌉ and the number of edges Δ⌈Δ/2⌉+⌊Δ/2⌋, D must be isomorphic to 𝒞. This proves (d).Proof of (e).
This follows from (d).Now we explore the inverse of Proposition10. Recall the connected graph 𝒞 described in Section 3.1 is the unique graph satisfying (4).Proposition 11.
LetG1 be a simple graph such that |E(G1)|=Δ(G1)ν(G1)+⌊ν(G1)/⌈Δ(G1)/2⌉⌋⌊Δ(G1)/2⌋, that is, G1 attains the maximum edge bound given by the inequality (1). If ν(G1)≥2, Δ(G1)≥2 and ⌈Δ(G1)/2⌉ does not divide ν(G1), then there exists a simple graph G2 such that |E(G2)|=|E(G1)|, ν(G2)=ν(G1), Δ(G2)=Δ(G1) and G2 is not  isomorphic to G1.Proof.
We use the method given in [5] to construct a simple graph G such that |E(G)|=|E(G1)|, ν(G)=ν(G1), and Δ(G)=Δ(G1). Let G have t:=ν(G1)-(⌈Δ(G1)/2⌉)⌊ν(G1)/⌈Δ(G1)/2⌉⌋ components isomorphic to K1,Δ(G1) and ⌊ν(G1)/⌈Δ(G1)/2⌉⌋ components isomorphic to 𝒞 (described in Section 3.1). Let G2=G if G1 is not isomorphic to G. So assume that G1 is isomorphic to G. Note that t:=ν(G1)-(⌈Δ(G1)/2⌉)⌊ν(G1)/⌈Δ(G1)/2⌉⌋≥1 as ⌈Δ(G1)/2⌉ does not divide ν(G1). If t≥2 then let H1 and H2 be two components of G1 isomorphic to K1,Δ(G1). We remove an edge of H1 and then connect the vertex of degree Δ(G1)-1 of H1 to any vertex of degree one in H2 by a new edge. Thus, a new graph G2 is obtained. It is obvious by construction that G2 satisfies hypothesis of Proposition 11. So, we need to consider only the case t=1 to complete the proof. As ν(G1)≥2 and t=1, G1 has at least two components. Hence G1 has a component isomorphic to K1,Δ(G1) and at least one component isomorphic to 𝒞. As Δ(G1)+|E(𝒞)|=Δ(G1)+Δ(G1)(⌈Δ(G1)/2⌉)+⌊Δ(G1)/2⌋≤⌊(2(⌈Δ(G1)/2⌉+1)+1)Δ(G1)/2⌋, we can coalesce the two components to form a factor-critical component with 2(⌈Δ(G1)/2⌉+1)+1 vertices and maximum degree at most Δ(G1) which has number of edges equal to Δ(G1)+|E(𝒞)| and maximum matching size equal to ν(𝒞)+1. Thus, again a new graph G2 is obtained. It is obvious by construction that G2 satisfies hypothesis of Proposition 11.We can combine the above two propositions in the following theorem.Theorem 12.
LetG be a simple graph such that ν(G)≥2, Δ(G)≥2 and |E(G)|=Δ(G)ν(G)+⌊ν(G)/⌈Δ(G)/2⌉⌋⌊Δ(G)/2⌋. G is a unique graph up to isomorphism if and only if ⌈Δ(G)/2⌉ divides ν(G).Proof.
The above conclusion follows by Propositions10 and 11.


## 4. Graphs Whose Edge Set Can Be Partitioned into Maximum Matchings

Definition 13.
A simple graphG is called friendly-edge-colorable if and only if E(G) has a partition into maximum matchings.
Examples:C4, C2m for m≥2, K2m for m≥1, K2m+1 for m≥1 and K1,n for n≥1.We observe that a proper edge coloring ofG is equivalent to partitioning E(G) into matchings (may not be maximum).Proposition 14.
G is a friendly-edge-colorable graph if and only if |E(G)|=χ′(G)ν(G).Proof.
We consider a minimal proper edge coloring ofG. Since every color class of G is a matching and a matching in G can be of size at most ν(G), we have |E(G)|≤χ′(G)ν(G). So if G is a friendly-edge-colorable graph, then there is a partition of E(G) into maximum matchings. Hence there is a positive integer n such that |E(G)|=nν(G). This partition corresponds to a proper edge coloring with n colors. Thus, χ′(G)≤n. Hence, |E(G)|=nν(G)≥χ′(G)ν(G). Thus for a friendly-edge-colorable graph G, we have |E(G)|=χ′(G)ν(G).
SupposeG is not a friendly-edge-colorable graph. We consider an edge coloring of G in χ′(G) colors. Note that each color class is a matching and at least one of the color classes is of size strictly less than ν(G) as G is not a friendly-edge-colorable graph. Thus, we get |E(G)|<χ′(G)ν(G).Proposition 15.
IfG is a friendly-edge-colorable graph, then any proper edge coloring of G in χ′(G) colors results in a partition of E(G) into maximum matchings.Proof.
Any proper edge coloring ofG is a partition of E(G) into matchings (may not be maximum). Consider a proper edge coloring of G in χ′(G) colors. If there is a color class of size strictly less than ν, then |E(G)|<χ′(G)ν(G) which contradicts Proposition 14.Remark 16.
The name “friendly-edge-colorable” is due to Proposition15 which states that when the least number of colors are used to properly color the edges, the colors are equally distributed so that each color class gets the maximum!
The following theorem characterizes friendly-edge-colorable graphs in Class II.Theorem 17.
LetG be a friendly-edge-colorable graph of Class II such that Δ(G)≥2 and ν(G)≥2. Then(a)
Δ(G) is even,(b)
Δ(G)/2 divides ν(G),(c)
every component ofG is isomorphic to KΔ(G)+1, the complete graph of order Δ(G)+1.Proof.
LetΔ=Δ(G) and ν=ν(G). By Proposition 15, |E(G)|=ν(Δ+1). Also by inequality (1),
(16)(Δ+1)ν=|E(G)|≤Δν+⌊ν⌈Δ/2⌉⌋⌊Δ2⌋,≤νΔ+ν⌈Δ/2⌉⌊Δ2⌋≤νΔ+ν,[as⌊Δ/2⌋⌈Δ/2⌉≤1].
Thus, ⌊ν/⌈Δ/2⌉⌋=ν/⌈Δ/2⌉, which proves (b). Also, ⌊Δ/2⌋/⌈Δ/2⌉=1 that implies (a). By Proposition 10, we know that every component of G is isomorphic to KΔ+1, the complete graph of order Δ+1.Now we will consider friendly-edge-colorable graphs that are in Class I, that is, graphs with edge chromatic indexΔ. Next we prove three lemmas that help us characterize friendly-edge-colorable graphs in Class I.Lemma 18.
LetG be a friendly-edge-colorable graph. If there exists a vertex x∈V(G) such that ν(G∖x)<ν(G) then degG(x)=χ′(G).Proof.
AsG is friendly-edge-colorable, there exists a partition of E(G) into maximum matchings and, by Proposition 14, |E(G)|/ν(G)=χ′(G). Hence each class, that is, each part of this partition, has size ν(G) and there are χ′(G) parts. We denote each color class (i.e., a part in the partion) by Ci for all i∈{1,…,χ′(G)}. If degG(x)<χ′(G) then there is a color missing at x. Without loss of generality, let the missing color be 1. Hence the whole color class C1 belongs to E(G∖x), that is, C1⊆E(G∖x). Therefore, ν(G∖x)≥|C1|. But C1 is a maximum matching of G hence |C1|=ν(G). This contradicts that ν(G∖x)<ν(G). Hence degG(x)≥χ′(G). Also degG(x)≤Δ(G)≤χ′(G) by the definition of χ′(G).Remark 19.
Lemma18 implies that if G is friendly-edge-colorable and there exists x∈V(G) such that ν(G∖x)<ν(G), then degG(x)=Δ(G)=χ′(G) as Δ(G)≤χ′(G). Hence G is in Class I. So the contrapositive implies that if G is friendly-edge-colorable and in Class II, that is, not in Class I, then ν(G∖x)=ν(G) for all x∈V(G). By Gallai’s lemma, each component of G is a factor-critical component as we noticed in Theorem 17.Lemma 20.
LetG be a friendly-edge-colorable graph. If there exists x∈V(G) such that ν(G∖x)<ν(G) and |E(G∖x)|≥1, then G∖x is a friendly-edge-colorable graph and χ′(G∖x)=χ′(G).Proof.
AsG is friendly-edge-colorable, E(G) has a partition into maximum matchings. Define a coloring, C, corresponding to such a partition. Then each color class has size ν(G) and there are |E(G)|/ν(G)=χ′(G) color classes by Proposition 14. Now consider the restriction of C on E(G∖x). By Lemma 18, degG(x)=χ′(G) hence CE(G∖x) has χ′(G) color classes each of size ν(G)-1. As by assumption ν(G∖x)=ν(G)-1, E(G∖x) has a partition into maximum matchings, implying that G∖x is friendly-edge-colorable. Since G∖x is friendly-edge-colorable, by Proposition 14, we get
(17)χ′(G∖x)=|E(G∖x)|ν(G∖x)=|E(G)|-degG(x)ν(G)-1=|E(G)|-χ′(G)ν(G)-1=ν(G)χ′(G)-χ′(G)ν(G)-1=χ′(G).By a nontrivial component of a simple graph, we shall mean a component that has at least an edge, that is,K2 is a subgraph of the component.Lemma 21.
G is a friendly-edge-colorable graph if and only if each nontrivial component C of G is friendly-edge-colorable and χ′(G)=χ′(C).Proof.
We first show the if part. Consider a proper edge coloring for each component inχ′(G) colors. This gives the desired partition of the edge set of G.
Next we show the only if part. SinceG is friendly-edge-colorable, there is a partition of E(G) into maximum matchings that has χ′(G) classes (by Proposition 14). We claim that restricting this partition to any component of G gives a partition of the edge set of the component into maximum matchings of the component. Suppose on the contrary that some matching ℳ𝒞 obtained this way (by restricting a maximum matching ℳ to 𝒞) for a component 𝒞 is not a maximum matching in 𝒞. Then there is an augmenting path relative to this matching in the component. But then this is an augmenting path, relative to the corresponding matching ℳ of G, in G. Hence ℳ is not a maximum matching of G. This contradicts the fact that ℳ is a maximum matching.
If for some componentC, χ′(C)≠χ′(G) then χ′(C)<χ′(G) (as χ′(C)≤χ′(G) for C is a component of G). Now consider any proper edge coloring of G in χ′(G) colors and for each component order color classes greedily. For each 1≤i≤χ′(G), we denote the ith color class by 𝒟(i). Then the first χ′(𝒞) color classes will have strictly larger size than the remaining color classes {𝒟(χ′(𝒞)+1),𝒟(χ′(𝒞)+2),…,𝒟(χ′(G))}. This contradicts that each color class is of the same size ν(G) as shown by Proposition 15.Remark 22.
In the previous lemma the condition thatχ′(G)=χ′(C) for all components C is necessary otherwise counter examples exist. For instance, let G be the graph consisting of two components one of which is K3 and the other one is K1,4.Theorem 23.
IfG is a nontrivial, Class I, friendly-edge-colorable graph then E(G) has a partition into the following two kinds of subgraphs:(i)
K1,Δ(G)(ii)
factor critical, friendly-edge-colorable graphs with edge chromatic indexχ′(G).Proof.
LetG0:=G. If there exists x1∈V(G) such that ν(G∖x1)<ν(G) then remove all edges incident to x1 and define G1:=G∖x1. Since by Lemma 18 and Remark 19  degG(x1)=Δ, we removed a K1,Δ(G) from G. Note that G1 is a friendly-edge -colorable graph and χ′(G1)=χ′(G) by Lemma 20. By Lemma 21, each component of G1 is also a friendly-edge-colorable graph and has edge chromatic index χ′(G). Similarly, for i≥1 define Gi:=Gi-1∖xi if there exists xi∈V(Gi-1) such that ν(Gi-1∖xi)<ν(Gi-1). We remove the vertices xi and all edges adjacent to each of these vertices. Corresponding to each of the xi’s, we get a subgraph isomorphic to K1,Δ(G). For some large enough i, we have only those nontrivial components C in Gi such that ν(C∖x)=ν(C) for all x∈V(C). By Gallai’s lemma, these are the factor critical components. Also by Lemma 21, χ′(C)=χ′(Gi)=χ′(G).Remark 24.
Reader can review Figure1 and notice that the degree of the vertex x in Figure 1 is 3 and x must be covered by every maximum matching. Also, removal of the vertex x from the graph yields a graph whose only nontrivial component is factor-critical.



---

*Source: 358527-2013-01-17.xml*