Maximal Edge-Colorings of Graphs

Abstract

A maximal edge-coloring of a graph G of order n is a proper edge-coloring of G with $\chi '(K_n)$ colors such that no edge of the complement $\overline{G}$ of G can be attached to G without violating conditions of a proper edge-coloring. We almost completely determine sets of all sizes of graphs which admit maximal edge-colorings.

1 Introduction

A maximal edge-coloring of a graph G of order n is a proper edge-coloring of G with $\chi '(K_n)$ colors such that no edge of the complement $\overline{G}$ of G can be attached to G without violating conditions of proper edge-coloring. For given n, a spectrum $\mathrm{MEC}(n)$ is defined to be the set of all sizes of graphs of order n which admit maximal edge-colorings. More precisely, $\mathrm{MEC}(n)=\{m:$ there exists a maximal edge-coloring of a graph G such that $|V(G)|=n$ and $|E(G)|=m\}$.

Various combinatorial objects were investigated in terms of maximality, cf. [4, 5]. One of the well examined cases concerns maximal partial latin squares [3]. A partial latin square of order n is an $n\times n$ array in which each cell is either empty or contains a single symbol from an n-element set S, such that each symbol occurs at most once in each row and at most once in each column. A partial latin square is maximal if no empty cell can be filled with an element of S. Evidently, a partial latin square of order n corresponds to a proper-edge coloring of a balanced bipartite graph $G=(V,U,E)$ with at most $n=\chi '(K_{n,n})$ colors, where $|U|=|V|=n$. Moreover, a proper edge-coloring of any graph may be represented as a symmetric partial latin square of order n, where both cells with coordinates (i, j) and (j, i), $i\ne j$, are either empty or contain the same symbol from S. In this way maximal edge-colorings of non-bipartite graphs make an obvious next case to be considered.

Let S be a sequence of edges of a graph G. An algorithm for a proper edge-coloring with a fixed number of colors is called on-line if, for each next term of S, it either colors an edge or reject it if no color is available. Maximally edge-colored graphs make a class of extremal graphs for the on-line edge-coloring problem, cf. [1, 2].

Let $e=|E(K_n)|={n \atopwithdelims ()2}$. Several constructions are used in order to prove main results.

Theorem 1

Let $n\ge 3$ and k be an integer such that $\frac{e}{2}+\frac{3}{4}(n-1)\le k\le e$ if n is odd and $\frac{e}{2}+\frac{n}{4}\le k\le e$ otherwise, except for $k=e-1$ when n is even and possibly $k=\frac{e}{2}+\frac{n}{4}+1$ when $n\equiv 2\pmod 4$ and $n\ge 10$. Then $k\in \mathrm{MEC}(n)$.

Theorem 2

Let $n\ge 3$. If $k\in \mathrm{MEC}(n)$ then $k>\frac{e}{2}-\frac{n}{8}$ for even n and $k\ge \frac{e}{2}$ otherwise.

A problem of determining $\mathrm{MEC}(n)$ remains open for narrow intervals: $(\frac{e}{2}-\frac{n}{8};\frac{e}{2}+\frac{n}{4})$ when n is even and $[\frac{e}{2};\frac{e}{2}+\frac{3}{4}(n-1))$ otherwise, and whether $\frac{e}{2}+\frac{n}{4}+1\in \mathrm{MEC}(n)$ when $n\equiv 2\pmod 4$ and $n\ge 10$. In the case of small orders, spectra for $\mathrm{MEC}(n)$ were completely verified with a computer. It turns out that, for $n\le 10$, each of the above intervals has empty intersection with $\mathrm{MEC}(n)$. Namely, $\mathrm{MEC}(3)=\{3\}$, $\mathrm{MEC}(4)=\{4,6\}$, $\mathrm{MEC}(5)=\{8,9,10\}$, $\mathrm{MEC}(6)=\{9,10,\ldots ,13,15\}$, $\mathrm{MEC}(7)=\{15,16,\ldots ,21\}$, $\mathrm{MEC}(8)=\{16,17,\ldots ,26,28\}$,$\mathrm{MEC}(9)=\{24,25,\ldots ,36\}$, $\mathrm{MEC}(10)=\{25,27,28,$ $\ldots ,43,45\}$.

In a usual way, we define a canonical proper edge-coloring of a complete graph $K_{2n}$ for every $n\ge 1$. Let $V(K_{2n})=\{0,1,\ldots ,2n-2\}\cup \{\infty \}$. The color classes are: $C_i=\{\{i-j,i+j\}:\; j=1,2,\ldots n-1\}\cup \{i,\infty \}$, $i=0,1,\ldots 2n-2$, where all labels of vertices are taken modulo $2n-1$. In other words, an edge $\{u,v\}$ gets color $(u+v)/2$ if both $u,v\ne \infty$ and an edge $\{u,\infty \}$ receives color u (colors are taken modulo $2n-1$). A canonical proper edge-coloring of $K_{2n-1}$, for each $n\ge 2$, can be obtained from a canonical coloring of $K_{2n}$ by removal of the vertex $\infty$ together with all its incident edges.

Let symbol $a_{p}(u,v)$ be defined as follows: $a_{p}(u,v)=(u+v)/2 \bmod p$ if both $u,v\ne \infty$ and $a_{p}(u,\infty )=a_{p}(\infty ,u)=u$.

We briefly say that a color i is missing at a vertex v if none of edges incident to v has color i; if an edge incident to v has color i then i is present at v.

2 Constructions

By definition of the maximal edge-coloring, $e\in \mathrm{MEC}(n)$.

Remark 3

For each even $n\ge 2$, $(e-1)\not \in \mathrm{MEC}(n)$.

Proof

Let n be even. Let G be a complete graph on n vertices with one edge $\{u,v\}$ removed. Let c be a proper edge-coloring of G with $n-1$ colors. Then each color except one, say d, forms a perfect matching in G so it is present at each vertex of G. Color d covers $\frac{n}{2}-1$ edges, thus it is missing at exactly two vertices of degree $n-2$, which are u and v. Then the edge $\{u,v\}$ can be colored with d and in this way c is not maximal. $\square$

It is easy to verify spectra for $n\le 4$.

Observation 4

$\mathrm{MEC}(3)=\{3\}$, $\mathrm{MEC}(4)=\{4,6\}$.

In what follows, each graph is constructed by coloring edges it contains.

Lemma 5

Let $n\ge 3$ and $2n^2-3n+1\le k\le 2n^2-n-2=|E(K_{2n})|-2$. Then $k\in \mathrm{MEC}(2n)$.

Proof

Let $V(G)=\overline{V} \cup \{\overline{\infty }\}$, where $\overline{V} =\{0,1,\ldots ,2n-2\}$. Let $l=2n^2-n-k-1$. Then $1\le l\le 2n-2$. All colors and indices of vertices are taken modulo $2n-1$.

First we color edges of a complete graph $K_{\overline{V}}$ with colors $0,1,\ldots ,$ $2n-2$, except for l edges $\{i,i+1\}$, where $i\in I=\{0,1,\ldots , \lfloor (l-1)/2\rfloor \}\cup \{n,n+1,\ldots ,n+\lfloor (l-2)/2\rfloor \}$; namely, each edge $\{u,v\}$ gets color $a_{2n-1}(u,v)$. Moreover, each edge $\{i,\overline{\infty }\}$, except for $\{n+(l-1)/2,\overline{\infty }\}$ if l is odd and $\{l/2,\overline{\infty }\}$ if l is even, gets color $i+n$ if $i\in I$, and color i otherwise.

Notice that at the vertex $\overline{\infty }$ the only missing color is 0. At each vertex i such that $i\in I$, color i does not appear. Moreover, at $i=n+(l-1)/2$ if l is odd and $i=l/2$ if l is even, color i is missing. At each vertex $i+1$, where $i\in I$, color $i+n$ remains unused. Thus none of $l+1$ edges which are not in E(G): $\{i,i+1\}$, where $i\in I$, and $\{n+(l-1)/2,\overline{\infty }\}$ if l is odd and $\{l/2,\overline{\infty }\}$ otherwise, can be colored. $\square$

Lemma 6

Let $n\ge 2$ and $2n^2-n+2\le k\le 2n^2+n-1=|E(K_{2n+1})|-1$. Then $k\in \mathrm{MEC}(2n+1)$.

Proof

Let $V(G)=\tilde{V} \cup \{\overline{\infty }\}$, where $\tilde{V} =\{ 0,1,\ldots ,2n-2\}\cup \{\infty \}$. Let $l=k-(2n^2-n+2)$. Then $0\le l\le 2n-3$. All colors and indices of vertices have to be taken modulo $2n-1$.

First we color edges of a complete graph $K_{\tilde{V}}$ induced on $\tilde{V}$ with colors $0,1,\ldots ,$ $2n-2,A,B$. An edge $\{i,i+1\}$, for $i=1,2,\ldots , l$, gets color A if i is odd and B otherwise. Each remaining edge $\{u,v\}$ of $K_{\tilde{V}}$ gets color $a_{2n-1}(u,v)$. Moreover, the edge $\{0,\overline{\infty }\}$ is colored with A and the edge $\{1,\overline{\infty }\}$ with B. Each edge $\{i,\overline{\infty }\}$, $i=2,3,\ldots , l+1$, can be colored with color $i-n$.

Notice that in the vertex $\infty$ colors A and B are missing. At each vertex i, where $i=1,2,\ldots , l$, color $i+n$ is missing. Moreover, for $i=l+2,l+3,\ldots ,2n-2$, both colors A and B do not appear at i. At the vertex $l+1$ color A is not present if l is even and color B otherwise. At the vertex 0 color B is missing. At the vertex $\overline{\infty }$, each color $i-n$, for $i=l+2,l+3,\ldots , 2n$, remains unused. Thus none of $2n-2-l$ edges $\{\infty ,\overline{\infty }\}$, $\{i,\overline{\infty }\}$, where $i=l+2,l+3,\ldots , 2n-2$, which do not belong to E(G), can be colored. $\square$

Lemma 7

Let $n\ge 1$ and $4n^2\le k\le 8n^2-2n-2=|E(K_{4n})|-2$. Then $k\in \mathrm{MEC}(4n)$.

Proof

The case when $k\ge 8n^2-6n+1=|E(K_{4n})|-4n+1$ follows by Lemma 5 and Observation 4. Thus we may assume that $k\le 8n^2-6n$.

Let $l=k-4n^2$. Then $0\le l\le 4n^2-6n$. Let $V(G)=\tilde{V}\times \{1,2\}$, where $\tilde{V}=\{0,1,\ldots ,(2n-2)\}\cup \{\infty \}$. To construct a graph G we begin with a canonical coloring of all edges of the complete graph $K_{\tilde{V}_1}$: an edge $\{u_1,v_1\}$ gets color $a_{2n-1}(u,v)$.

First we consider the case when l is even. We choose a set S of l / 2 edges of $K_{\tilde{V}_1}$. For each edge $\{u_1,v_1\}\in S$, we color an edge $\{u_2,v_2\}$ with color $a_{2n-1}(u,v)$ and moreover two edges $\{u_1,v_2\}$ and $\{u_2,v_1\}$, both with color $a_{2n-1}(u,v)+2n$. Each remaining edge $\{u_2,v_2\}$ of $K_{\tilde{V}_2}$, which is not colored yet, gets color $a_{2n-1}(u,v)+2n$. Moreover, each edge $\{u_1,u_2\}$, where $u\in \tilde{V}$, gets color $2n-1$.

Obviously, we cannot color any of edges of $K_{4n}$ that are missing in G (which are of the form $\{u_1,v_2\}$, where $u,v\in \tilde{V}$) since each color $0,1,\ldots 2n-1$ appears at each vertex of $\tilde{V}_1$ as a color of its incident edges, and moreover each color $2n-1,2n,\ldots 4n-2$ is present at each vertex of $\tilde{V}_2$.

Assume now that l is odd. The edge $\{0_2,\infty _2\}$ gets color 0. Then the edges $\{0_1,0_2\}$ and $\{1_1,\infty _2\}$ are colored with color 2n. We choose a subset S of $(l-1)/2$ edges of the set $E(K_{\tilde{V}_1}){\setminus } \{\{0_1,\infty _1\}, \{1_1,(2n-2)_1\},\{1_1,\infty _1\}\}$. For each edge $\{u_1,v_1\}\in S$, we color an edge $\{u_2,v_2\}$ with color $a_{2n-1}(u,v)$ and moreover two edges $\{u_1,v_2\}$ and $\{u_2,v_1\}$, both with color $a_{2n-1}(u,v)+2n$. Each edge $\{u_2,v_2\}$ of $K_{\tilde{V}_2}$ which is still uncolored gets color $a_{2n-1}(u,v) + 2n$. Finally, all edges $\{u_1,u_2\}$, where $u=1,2,\ldots 2n-2,\infty$, get color $2n-1$.

The same argument as above guarantees that none of the edges missing in G can be colored. Namely, each color $0,1,\ldots 2n-2$ appears at each vertex of $\tilde{V}_1$, each color $2n,\ldots 4n$ is present at each vertex of $\tilde{V}_2$, and moreover the only two vertices of G which are not incident with an edge of color $2n-1$ are $0_1$ and $0_2$ but the edge $\{0_1,0_2\}$ is already in G. $\square$

Lemma 8

Let $n\ge 1$ and $4n^2+4n\le k\le 8n^2+2n-1=|E(K_{4n+1})|-1$. Then $k\in \mathrm{MEC}(4n+1)$.

Proof

The case when $k\ge 8n^2-2n+2=|E(K_{4n+1})|-4n+2$ follows by Lemma 6. Thus we may assume that $k\le 8n^2-2n+1$.

Let $l=k-4n^2-4n$. Then $0\le l\le 4n^2-6n+1$. Let $V(G)=\overline{V}_1\cup \overline{V}_2\cup \{ \infty \}$, where $\overline{V}_1=\{0_1,1_1,\ldots ,(2n-2)_1\}$ and $\overline{V}_2=\{0_2,1_2,\ldots ,(2n)_2\}$. Let $\tilde{V}_i=\overline{V}_i\cup \{\infty \}$, $i=1,2$. We start with a canonical coloring of all edges of the complete graph $K_{\tilde{V}_1}$: an edge $\{u,v\}$ gets color $a_{2n-1}(u,v)$.

Assume that l is even. We choose a set S of l / 2 edges of $K_{\overline{V}_1}$. For each edge $\{u_1,v_1\} \in S$, we color an edge $\{u_2,v_2\}$ with color $a_{2n-1}(u,v)$ and two edges $\{ u_1,v_2\}$ and $\{ u_2,v_1\}$ with $a_{2n+1}(u,v)+2n$. Next we color all edges of $K_{\tilde{V}_2}$ which are not colored yet: an edge $\{u,v\}$ gets color $a_{2n+1}(u,v)+2n$. Moreover, all edges $\{u_1,u_2\}$, where $u=0,1,\ldots 2n-2$, are colored with the same color $2n-1$.

The only edges missing in G are of the form $\{ u_1,v_2\}$, where $u_1\in \overline{V}_1$ and $u_2\in \overline{V}_2$. They cannot be colored since all colors $0,1,\ldots 2n-1$ are present at each vertex of $\overline{V}_1$ and all colors $2n,\ldots 4n$ appear at each vertex of $\overline{V}_2$.

Now we consider the case when l is odd. First, we color three edges: $\{\infty , 0_2\}$ with color $2n-1$, $\{ 0_1,0_2\}$ with color 2n and $\{ 0_1,(2n-1)_2\}$ with color $2n-1$. Next we choose a subset S of $(l-1)/2$ edges of $K_{\overline{V}_1}$. For each edge $\{ u_1,v_1\} \in S$, we color an edge $\{ u_2,v_2\}$ with $a_{2n-1}(u,v)$ and two edges $\{ u_1,v_2\}$ and $\{ u_2,v_1\}$ with color $a_{2n+1}(u,v)+2n$. Each edge $\{u,v\}$ of $K_{\tilde{V}_2}$, which is not colored yet, gets color $a_{2n+1}(u,v)+2n$. Moreover, each edge $\{ u_1,u_2\}$, where $u=1,2,\ldots ,2n-2$, gets color $2n-1$.

Notice that each color $0,1,\ldots 2n-2$ appears at each vertex of $\tilde{V}_1$ and each color $2n+1,2n+2,\ldots 4n$ is present at each vertex of $\tilde{V}_2$. Color $2n-1$ is missing only at the vertex $(2n)_2$ and color 2n only at $\infty$. All edges which are missing in G are of the form $\{ u_1,v_2\}$, where $u_1\in \overline{V}_1$, $v_2\in \overline{V}_2$, so none of them can be colored. $\square$

Lemma 9

Let $n\ge 1$ and $4n^2+4n+1\le k\le 8n^2+6n-1=|E(K_{4n+2})|-2$, $k\ne 4n^2+4n+2$. Then $k\in \mathrm{MEC}(4n+2)$.

Proof

The case when $k\ge 8n^2+2n=|E(K_{4n+2})|-4n-1$ follows by Lemma 5. Thus we may assume that $k\le 8n^2+2n-1$.

Let $l=k-4n^2-4n-1$. Then $0\le l\le 4n^2-2n-2$. Let $V(G)=\tilde{V}_1\cup \tilde{V}_2$, where $\tilde{V}_1=\{0_1,1_1,\ldots ,(2n-2)_1\}\cup \{\infty _1\}$ and $\tilde{V}_2=\{0_2,1_2,\ldots ,(2n)_2\}\cup \{\infty _2\}$. To construct a graph G we use a similar scheme as in Lemmas 7 and 8. We begin with a canonical coloring of all edges of the complete graph $K_{\tilde{V}_1}$: an edge $\{u_1,v_1\}$ gets color $a_{2n-1}(u,v)$.

Consider the case when l is even. First we choose a set S of l / 2 edges of $K_{\tilde{V}_1}$. For each edge $\{u_1,v_1\}\in S$, we color an edge $\{u_2,v_2\}$ with color $a_{2n-1}(u,v)$ and moreover two edges $\{u_1,v_2\}$ and $\{u_2,v_1\}$, both with color $a_{2n+1}(u,v)+2n$. Each remaining edge $\{u_2,v_2\}$ of $K_{\tilde{V}_2}$, which is so far uncolored, gets color $a_{2n+1}(u,v)+2n$. Moreover, each edge $\{u_1,u_2\}$, where $u=0,1,\ldots ,2n-2,\infty$, gets color $2n-1$.

We cannot color any of edges of $K_{4n+2}$ that are missing in G (which are of the form $\{u_1,v_2\}$, where $u_1\in \tilde{V}_1$ and $v_2\in \tilde{V}_2$) since all colors $0,1,\ldots 2n-1$ appear at each vertex of $\tilde{V}_1$ and moreover all colors $2n,\ldots 4n$ are present at each vertex of $\tilde{V}_2$.

We assume now that l is odd. Then $3\le l\le 4n^2-2n-3$. The edge $\{(n-1)_2,\infty _2\}$ is colored with color $n-1$. Then four edges $\{0_1,\infty _2\}$, $\{(n-1)_1,(n-1)_2\}$, $\{\infty _1,(2n-1)_2\}$ and $\{(2n-2)_1,(2n)_2\}$ get the same color $3n-1$. The edge $\{(2n-1)_2,(2n)_2\}$ is colored with $2n-1$. Now we choose a subset S of $(l-3)/2$ edges of the set $E(K_{\tilde{V}_1}){\setminus } \{\{0_1,\infty _1\}, \{0_1,(2n-2)_1\},\{(n-1)_1,\infty _1\}\}$. For each edge $\{u_1,v_1\}\in S$, we color an edge $\{u_2,v_2\}$ with color $a_{2n-1}(u,v)$ and moreover two edges $\{u_1,v_2\}$ and $\{u_2,v_1\}$, both with color $a_{2n+1}(u,v)+2n$. Each remaining edge $\{u_2,v_2\}$ of $K_{\tilde{V}_2}$, which is still uncolored, gets color $a_{2n+1}(u,v)+2n$. Finally, all edges $\{u_1,u_2\}$, where $u=0,1,\ldots ,n-2,n,n+1,\ldots ,2n-2,\infty$, get color $2n-1$.

The same argument as above guarantees that none of the edges which are missing in G can be colored. Namely, each color $0,1,\ldots 2n-2$ appears at each vertex of $\tilde{V}_1$, each color $2n,\ldots 4n$ is present at each vertex of $\tilde{V}_2$, and moreover the only two vertices of G which are not incident with an edge of color $2n-1$ are $(n-1)_1$ and $(n-1)_2$ but the edge $\{(n-1)_1,(n-1)_2\}$ is already in G. $\square$

Lemma 10

Let $n\ge 1$ and $4n^2+8n+3\le k\le 8n^2+10n+2=|E(K_{4n+3})|-1$. Then $k\in \mathrm{MEC}(4n+3)$.

Proof

The case when $k\ge 8n^2+6n+3=|E(K_{4n+3})|-4n$ follows by Lemma 6. Thus we may assume that $k\le 8n^2+6n+2$.

Let $l=k-(4n^2+8n+3)$. Then $0\le l\le 4n^2-2n-1$. Let $V(G)=(\overline{V}\times \{1,2\})\cup \{\infty \}$, where $\overline{V}=\{0,1,\ldots ,2n\}$. We denote $\tilde{V}_i=\overline{V}_i\cup \{\infty \}$, $i=1,2$. To construct a graph G we begin with a canonical coloring of all edges of the complete graph $K_{\tilde{V}_1}$: an edge $\{u,v\}$ gets color $a_{2n+1}(u,v)$.

First we consider the case when l is even. We choose a set S of l / 2 edges of $K_{\overline{V}_1}$. For each edge $\{u_1,v_1\}\in S$, an edge $\{u_2,v_2\}$ gets color $a_{2n+1}(u,v)$ and moreover we color two edges $\{u_1,v_2\}$ and $\{u_2,v_1\}$, both with $a_{2n+1}(u,v)+2n+2$. Each remaining edge $\{u_2,v_2\}$ of $K_{\tilde{V}_2}$, which is not colored yet, gets color $a_{2n+1}(u,v)+2n+2$. Moreover, each edge $\{u_1,u_2\}$, where $u\in \overline{V}$, gets color $2n+1$.

The only missing edges in G are of the form $\{u_1,v_2\}$ where $u,v\in \overline{V}$. Each color $0,1,\ldots 2n$ appears at each vertex of $\tilde{V}_1$; similarly, each color $2n+2,2n+3,\ldots 4n+2$ appears at each vertex of $\tilde{V}_2$. Moreover, color $2n+1$ is present at each vertex of V(G) except for $\infty$. Therefore no edge can be attached to G without violating proper edge coloring.

Assume now that l is odd. The edge $\{1_2,(2n)_2\}$ gets color 0. Then the edges $\{1_1,1_2\}$ and $\{0_1,(2n)_2\}$ are colored with color $2n+2$. Now we choose a subset S of $(l-1)/2$ edges of the set $E(K_{\overline{V}_1}){\setminus } \{\{1_1,(2n)_1\},\{0_1,(2n)_1\}\}$. For each edge $\{u_1,v_1\}\in S$, we color an edge $\{u_2,v_2\}$ with color $a_{2n+1}(u,v)$ and moreover two edges $\{u_1,v_2\}$ and $\{u_2,v_1\}$, both with color $a_{2n+1}(u,v)+2n+2$. Each edge $\{u_2,v_2\}$ of $K_{\tilde{V}_2}$ which is still uncolored gets color $a_{2n+1}(u,v) + 2n+2$. Finally, all edges $\{u_1,u_2\}$, where $u=0,2,3,\ldots 2n$, get color $2n+1$.

Analogously as in the previous case, the only missing edges are of the form $\{u_1, v_2\}$, where $u,v\in \overline{V}$. All colors $0,1,\ldots ,2n$ appear at each vertex of $\tilde{V}_1$; all colors $2n+2,2n+3, \ldots ,4n+2$ appear at each vertex of $\tilde{V}_2$. Color $2n+1$ is missing only at the vertices $\infty ,1_1,1_2$, however the edges $\{1_1, \infty \}$, $\{1_2,\infty \}$ and $\{1_1,1_2\}$ are already colored. $\square$

Proof of Theorem 1

The assertion is concluded from Lemmas 7–10 and Observation 4. $\square$

Notice that, in the most cases, an example of a maximal edge-colored graph of odd order $2n-1$ may be obtained from a corresponding example of order 2n by gluing two carefully chosen vertices.

3 Lower Bound

Lemma 11

For all positive integers $a_1, \ldots ,a_k\ge 2$ and $k\ge 1$, the following inequality holds

$$\begin{aligned} k{\frac{a_1+a_2+\cdots +a_k}{k}\atopwithdelims ()2}\le \sum _{i=1}^{k} {a_i\atopwithdelims ()2}. \end{aligned}$$

Proof

Since $f(x)={x\atopwithdelims ()2}$ is a convex function, the assertion can be easily derived from the Jensen’s inequality. $\square$

In what follows, for a graph $G=(V,E)$ with $V=\{ v_1,v_2,\ldots ,v_n\}$, we denote a degree of a vertex $v_i$ by $x_i$, cardinality of E by m, and $\overline{x}=\frac{\sum _{i=1}^nx_i}{n}=\frac{2m}{n}$.

Lemma 12

Let $n\ge 2$. Then

$$\begin{aligned} \sum _{v_iv_j\in E} \min (n-x_i,n-x_j)\le m(n-\overline{x}). \end{aligned}$$

Proof

The above inequality is equivalent to $\sum _{v_iv_j\in E}(n+\min (-x_i,-x_j))\le mn-m\overline{x}$ and, by further simplification, to $\sum _{v_iv_j\in E}(\max (x_i,x_j)-\overline{x})\ge 0$. Since $\max (x_i,x_j)\ge \frac{x_i+x_j}{2}$, we get

$$\begin{aligned} \sum _{v_iv_j\in E}(\max (x_i,x_j)-\overline{x})\ge & {} \sum _{v_iv_j\in E}\left( \frac{x_i+x_j}{2}-\overline{x}\right) \\= & {} \frac{1}{2}\sum _{v_iv_j\in E}((x_i-\overline{x})+(x_j-\overline{x}))=\frac{1}{2}\sum _{i=1}^n x_i(x_i-\overline{x}). \end{aligned}$$

Let $A=\{ v_i\in V : \; x_i<\overline{x}\}$, $B=\{ v_i\in V: \; x_i\ge \overline{x}\}$ and $\widetilde{x}=\max _{x_i\in A}(x_i)$.

Then

$$\begin{aligned} \frac{1}{2}\sum _{i=1}^n x_i(x_i-\overline{x})= & {} \frac{1}{2}\sum _{v_i\in A} x_i(x_i-\overline{x})+\frac{1}{2}\sum _{v_i\in B} x_i(x_i-\overline{x}) \\= & {} \frac{1}{2}\sum _{v_i\in A} (x_i-\widetilde{x})(x_i-\overline{x})+\frac{1}{2}\sum _{v_i\in B} (x_i-\widetilde{x})(x_i-\overline{x}) \\&+\;\frac{1}{2}\sum _{i=1}^n \widetilde{x}(x_i-\overline{x}). \end{aligned}$$

For each vertex $v_i\in A$, $x_i-\widetilde{x}\le 0$ and $x_i-\overline{x}<0$. Similarly, for each vertex $v_i\in B$, $x_i-\widetilde{x}>0$ and $x_i-\overline{x}\ge 0$. Moreover, $\sum _{i=1}^n(x_i-\overline{x})=0$, what completes the proof. $\square$

In an analogous way we may prove the next result.

Lemma 13

Let G be a graph on a vertex set $V=\{ v_1,v_2,\ldots ,v_n\}$ with an edge set E. Then

$$\begin{aligned} \sum _{v_iv_j\in E} \min (n-1-x_i,n-1-x_j)\le m(n-1-\overline{x}). \end{aligned}$$

$\square$

We say that an edge $v_iv_j$ is forced in G if there exists a color that is missing both in $v_i$ and $v_j$.

Proof of Theorem 2

Let n be even. We assume that G admits a maximal edge-coloring c with $n-1$ colors. Let $y_i$ denote the number of edges with color i and $\overline{y}=\frac{\sum _{i=1}^{n-1}y_i}{n-1}=\frac{m}{n-1}$. Notice that $n-2y_i$ vertices are not incident with an edge colored with i. Due to maximality of c, all these vertices have to induce a clique in G. That is, color i forces ${n-2y_i}\atopwithdelims ()2$ edges. Obviously, some edges may be forced by more than one color. On the other hand, $n-1-x_i$ colors are missing at vertex $v_i$. Thus every edge $v_iv_j$ is forced at most $\min (n-1-x_i, n-1-x_j)$ times. Hence

$$\begin{aligned} \sum _{i=1}^{n-1} {n-2y_i\atopwithdelims ()2}\le \sum _{v_iv_j\in E}\min (n-1-x_i, n-1-x_j). \end{aligned}$$

By Lemmas 11 and 13 we get

$$\begin{aligned} (n-1) {n-2\overline{y}\atopwithdelims ()2}\le & {} \sum _{i=1}^{n-1} {n-2y_i\atopwithdelims ()2}\le \sum _{v_iv_j\in E}\min (n-1-x_i, n-1-x_j)\\\le & {} m(n-1-\overline{x}). \end{aligned}$$

After simple transformations we get $m\ge \frac{n^3-2n^2+n}{4n-2}=\frac{n^2}{4}-\frac{3n}{8}+\frac{n}{16n-8}>\frac{n^2}{4}-\frac{3n}{8}= \frac{e}{2}-\frac{n}{8}$.

Now we consider the case when n is odd. We assume that G admits a maximal edge-coloring c with n colors. In a similar way as in the previous case, let $y_i$ stand for the number of edges with color i and $\overline{y}=\frac{\sum _{i=1}^{n}y_i}{n}=\frac{m}{n}$. By the same argument as above, each color i forces ${n-2y_i}\atopwithdelims ()2$ edges. Moreover, at a vertex $v_i$ the number of missing colors is $n-x_i$, so every edge $v_iv_j$ can be forced at most $\min (n-x_i, n-x_j)$ times. By Lemmas 11 and 12,

$$\begin{aligned} n {n-2\overline{y}\atopwithdelims ()2}\le \sum _{i=1}^{n}{n-2y_i\atopwithdelims ()2}\le \sum _{v_iv_j\in E}\min (n-x_i, n-x_j)\le m(n-\overline{x}). \end{aligned}$$

Finally we get $m\ge \frac{n^2-n}{4}=\frac{e}{2}$. $\square$