On the number of edges of a graph and its complement

Dammak, Jamel; Lopez, Gerard; Kaddour, Hamza Si

doi:10.1016/j.ajmsc.2019.05.006

Let $G = (V, E)$ be a graph. The complement of $G$ is the graph $\bar{G} : = (V, {[V]}^{2} \ E)$ where ${[V]}^{2}$ is the set of pairs ${x, y}$ of distinct elements of $V$ ⁠. If $K$ is a subset of $V$ ⁠, the restriction of $G$ to $K$ is the graph $G_{↾ K} : = (K, {[K]}^{2} \cap E)$ ⁠. We prove that if $G = (V, E)$ is a graph and $k$ is an integer, $2 \leq k \leq v - 2$ ⁠, then there is a $k$ -element subset $K$ of $V$ such that $e ({\bar{G}}_{↾ K}) \neq e (G_{↾ K})$ ⁠, moreover the condition $k \leq v - 2$ is optimal. We also study the case $e ({\bar{G}}_{↾ K}) ≢ e (G_{↾ K}) (m o d p)$ where $p$ is a prime number. Following a question from M.Pouzet, we show this: Let $G = (V, E)$ be a graph with $v$ vertices. If $e (G) \neq e (\bar{G})$ (resp. $e (G) = e (\bar{G})$ ⁠) then there is an increasing family ${(H_{n})}_{2 \leq n \leq v}$ (resp. ${(H_{n})}_{2 \leq n \leq v - 2}$ ⁠) of $n$ -element subsets $H_{n}$ of $V$ such that $e (G_{↾ H_{n}}) \neq e ({\bar{G}}_{↾ H_{n}})$ for all $n$ ⁠. Similarly if $e (G) ≢ e (\bar{G}) (m o d p)$ where $p$ is a prime number, $p > v - 2$ ⁠, then there is an increasing family ${(H_{n})}_{2 \leq n \leq v}$ of $n$ -element subsets $H_{n}$ of $V$ such that $e (G_{↾ H_{n}}) ≢ e ({\bar{G}}_{↾ H_{n}}) (m o d p)$ for all integer $n \in {2,3, \dots, v}$ ⁠.

1. Introduction

Our notations and terminology follow [2]. A graph is an ordered pair $G : = (V, E)$ (or $(V (G), E (G))$ ⁠), where $E$ is a subset of ${[V]}^{2}$ ⁠, the set of pairs ${x, y}$ of distinct elements of $V$ ⁠. Elements of $V$ are the vertices of $G$ and elements of $E$ are its edges. An edge ${x, y}$ is also noted by $x y$ ⁠. The cardinality $| V |$ of $V$ is called the order of $G$ ⁠. Two distinct vertices $x$ and $y$ are adjacent if $x y \in E (G)$ ⁠, otherwise $x$ and $y$ are non-adjacent. We denote by $e (G) : = | E (G) |$ the number of edges of $G$ ⁠. The degree of a vertex $x$ of $G$ ⁠, denoted by $d_{G} (x)$ ⁠, is the number of edges which contain $x$ ⁠. The graph $G$ is $δ$ -regular (or regular) if $d_{G} (x) = δ$ for all $x \in V$ ⁠; $δ$ is called the degree of the regular graph $G$ ⁠. The complement of $G$ is the graph $\bar{G} : = (V, {[V]}^{2} \ E)$ ⁠. If $K$ is a subset of $V$ ⁠, the restriction of $G$ to $K$ ⁠, also called the induced subgraph of $G$ on $K$ ⁠, is the graph $G_{↾ K} : = (K, {[K]}^{2} \cap E)$ ⁠. For instance, given a set $V$ ⁠, $(V, ø)$ is the empty graph on $V$ whereas $(V, {x y : x \neq y \in V})$ is the complete graph.

Our first result is Theorem 1.1, we prove that: given a graph $G = (V, E)$ and $k$ be an integer, $2 \leq k \leq v - 2$ ⁠, we cannot have $e ({\bar{G}}_{↾ K}) = e (G_{↾ K})$ for all $k$ -element subsets $K$ of $V$ ⁠, moreover the condition $k \leq v - 2$ is optimal, indeed for $k = v - 1$ a counterexample is given by (2) of Theorem 1.1.

Theorem 1.1.

Let $G = (V, E)$ be a graph of order $v$ .

If $v \geq 4$ , then for each integer $k$ with $2 \leq k \leq v - 2$ , there is a $k$ -element subset $K$ of $V$ such that $e ({\bar{G}}_{↾ K}) \neq e (G_{↾ K})$ .
If $G$ is regular with degree $\frac{v - 1}{2}$ then $e (G) = e (\bar{G})$ and $e (\bar{G} - x) = e (G - x)$ for all vertex $x$ ⁠.
Let $p$ be a prime number with $p \geq 3$ such that $2 d_{G} (x) \equiv v - 1 (m o d p)$ for all $x \in V$ . Then $e (G) \equiv e (\bar{G}) (m o d p)$ and $e (\bar{G} - x) \equiv e (G - x) (m o d p)$ for all vertex $x$ ⁠.

Our second result is Theorem 1.2. Given a graph $G = (V, E)$ ⁠, $p$ a prime number, and $k$ an integer, $2 \leq k \leq v - 2$ ⁠, under some conditions on $k$ ⁠, we cannot have $e ({\bar{G}}_{↾ K}) \equiv e (G_{↾ K}) (m o d p)$ for all $k$ -element subsets $K$ of $V$ ⁠.

Theorem 1.2.

Let $G = (V, E)$ be a graph with $v \geq 4$ vertices and let $p$ be a prime number. Let $k$ be an integer, $2 \leq k \leq v - 2$ .

If ( $p = 2$ and $k \equiv 2 (m o d 4)$ ) or ( $p \geq 3$ and $k ≢ 0,1 (m o d p)$ ), then there is a $k$ -element subset $K$ of $V$ such that $e ({\bar{G}}_{↾ K}) ≢ e (G_{↾ K}) (m o d p)$ ⁠.
If $p \geq 3$ and $k \equiv 0 (m o d p)$ then there is a $k$ -element subset $K$ of $V$ such that $e ({\bar{G}}_{↾ K}) ≢ e (G_{↾ K}) (m o d p)$ if and only if $G$ is neither the complete graph nor the empty graph.

Our third result is Theorem 1.3. It is related to a question that M.Pouzet asked us about the existence, in a graph $G = (V, E)$ ⁠, of an increasing family ${(H_{n})}_{n}$ of $n$ -element subsets $H_{n}$ of $V$ such that $e (G_{↾ H_{n}}) \neq e ({\bar{G}}_{↾ H_{n}})$ ⁠.

Theorem 1.3.

Let $G = (V, E)$ be a graph of $v$ vertices with $v \geq 3$ .

If $e (G) \neq e (\bar{G})$ then there is a vertex $x$ such that $e (G - x) \neq e (\bar{G} - x)$ ⁠.
If $e (G) \neq e (\bar{G})$ then there is an increasing family ${(H_{n})}_{2 \leq n \leq v}$ of $n$ -element subsets $H_{n}$ of $V$ such that $e (G_{↾ H_{n}}) \neq e ({\bar{G}}_{↾ H_{n}})$ for all integer $n \in {2,3, \dots, v}$ ⁠.
If $e (G) = e (\bar{G})$ and $v \geq 4$ then there is an increasing family ${(H_{n})}_{2 \leq n \leq v - 2}$ of $n$ -element subsets $H_{n}$ of $V$ such that $e (G_{↾ H_{n}}) \neq e ({\bar{G}}_{↾ H_{n}})$ for all integer $n \in {2,3, \dots, v - 2}$ ⁠.
Let $p$ be a prime number, $p > v - 2$ . If $e (G) ≢ e (\bar{G}) (m o d p)$ then there is an increasing family ${(H_{n})}_{2 \leq n \leq v}$ of $n$ -element subsets $H_{n}$ of $V$ such that $e (G_{↾ H_{n}}) ≢ e ({\bar{G}}_{↾ H_{n}}) (m o d p)$ for all integer $n \in {2,3, \dots, v}$ ⁠.

2. Incidence matrices

We consider the matrix $W_{t k}$ defined as follows: Let $V$ be a finite set, with $v$ elements. Given non-negative integers $t, k$ ⁠, let $W_{t k}$ be the $(\begin{matrix} v \\ t \end{matrix})$ by $(\begin{matrix} v \\ k \end{matrix})$ matrix of $0$ ’s and $1$ ’s, the rows of which are indexed by the $t$ -element subsets $T$ of $V$ ⁠, the columns are indexed by the $k$ -element subsets $K$ of $V$ ⁠, and where the entry $W_{t k} (T, K)$ is $1$ ⁠. $T \subseteq K$ and is $0$ otherwise. The matrix transpose of $W_{t k}$ is denoted ^t $W_{t k}$ ⁠.

A fundamental result, due to D.H. Gottlieb [4], and independently W. Kantor [5], is this:

Theorem 2.1

(D.H. Gottlieb [4], W. Kantor [5]). For $t \leq m i n (k, v - k)$ , $W_{t k}$ has full row rank over the field $ℚ$ of rational numbers.

It is clear that $t \leq m i n (k, v - k)$ implies $(\begin{matrix} v \\ t \end{matrix}) \leq (\begin{matrix} v \\ k \end{matrix})$ then, from Theorem 2.1, we have the following result.

Corollary 2.2.

For $t \leq m i n (k, v - k)$ , the rank of $W_{t k}$ over the field $ℚ$ of rational numbers is $(\begin{matrix} v \\ t \end{matrix})$ and thus $K e r (^{t} W_{t k}) = {0}$ .

Corollary 2.2 and the following theorem are important tools in the proof of our main results. In fact, Theorem 2.3 has made to establish a version modulo a prime of Kelly’s combinatorial lemma [6]; it also allows to obtain a version modulo a prime of the particular version of Pouzet’s combinatorial lemma [7].

Let $n, p$ be positive integers, the decomposition of $n = \sum_{i = 0}^{n (p)} n_{i} p^{i}$ in the basis $p$ is also denoted by ${[n_{0}, n_{1}, \dots, n_{n (p)}]}_{p}$ where $n_{n (p)} \neq 0$ if and only if $n \neq 0$ ⁠.

Theorem 2.3

[1]. Let $p$ be a prime number. Let $v, t$ and $k$ be non-negative integers, $k = {[k_{0}, k_{1}, \dots, k_{k (p)}]}_{p}$ , $t = {[t_{0}, t_{1}, \dots, t_{t (p)}]}_{p}$ , $t \leq m i n (k, v - k)$ . We have:

$k_{j} = t_{j}$ for all $j < t (p)$ and $k_{t (p)} \geq t_{t (p)}$ if and only if $K e r (^{t} W_{t k}) = {0}$ (mod $p$ ).
$t = t_{t (p)} p^{t (p)}$ and $k = \sum_{i = t (p) + 1}^{k (p)} k_{i} p^{i}$ if and only if $d K e r (^{t} W_{t k}) = 1$ (mod $p$ ) and ${(1,1, \dots, 1)}$ is a basis of $K e r (^{t} W_{t k})$ ⁠.

The notation $a | b$ (resp. $a ł b$ ⁠) means $a$ divide $b$ (resp. $a$ not divide $b$ ⁠).

Theorem 2.4

(Lucas’ Theorem [3]). Let $p$ be a prime number, $t, k$ be positive integers, $t \leq k$ , $t = {[t_{0}, t_{1}, \dots, t_{t (p)}]}_{p}$ and $k = {[k_{0}, k_{1}, \dots, k_{k (p)}]}_{p}$ . Then

(\begin{matrix} k \\ t \end{matrix}) = \prod_{i = 0}^{t (p)} (\begin{matrix} k_{i} \\ t_{i} \end{matrix}) (m o d p), w h e r e (\begin{matrix} k_{i} \\ t_{i} \end{matrix}) = 0 i f t_{i} > k_{i} .

The following result is a consequence of Lucas’ theorem.

Corollary 2.5

([1]). Let $p$ be a prime number, $t, k$ be positive integers, $t \leq k$ , $t = {[t_{0}, t_{1}, \dots, t_{t (p)}]}_{p}$ and $k = {[k_{0}, k_{1}, \dots, k_{k (p)}]}_{p}$ . Then:

p | (\begin{array}{l} k \\ t \end{array}) i f a n d o n l y i f t h e r e i s i \in {0,1, \dots, t (p)} s u c h t h a t t_{i} > k_{i} .

3. Proofs of main results

Let $G = (V, E)$ be a graph of order $v$ ⁠. Let $T_{1}, T_{2}, \dots, T_{(\begin{matrix} v \\ 2 \end{matrix})}$ be an enumeration of the $2$ -element subsets of $V$ ⁠, let $K_{1}, K_{2}, \dots, K_{(\begin{matrix} v \\ k \end{matrix})}$ be an enumeration of the $k$ -element subsets of $V$ ⁠. Let $w_{G}$ be the row matrix $(g_{1}, g_{2}, \dots, g_{(\begin{matrix} v \\ 2 \end{matrix})})$ where $g_{i} = 1$ if $T_{i}$ is an edge of $G$ ⁠, $0$ otherwise. We have $w_{G} W_{2 k} = (e (G_{↾ K_{1}}), e (G_{↾ K_{2}}), \dots, e (G_{↾ K_{(\begin{matrix} v \\ k \end{matrix})}}))$ ⁠.

Note that $w_{\bar{G}} = (\bar{g_{1}}, \bar{g_{2}}, \dots, {\bar{g}}_{(\begin{matrix} v \\ 2 \end{matrix})})$ with $\bar{g_{i}} = 0$ if $T_{i}$ is an edge of $G$ ⁠, $1$ otherwise. We have $w_{\bar{G}} W_{2 k} = (e ({\bar{G}}_{↾ K_{1}}), e ({\bar{G}}_{↾ K_{2}}), \dots, e ({\bar{G}}_{↾ K_{(\begin{matrix} v \\ k \end{matrix})}}))$ ⁠.

3.1 Proof of Theorem 1.1

(1) Assume that $e ({\bar{G}}_{↾ K}) = e (G_{↾ K})$ for all $k$ -element subsets $K$ of $V$ ⁠, then $w_{G} W_{2 k} = w_{\bar{G}} W_{2 k}$ ⁠. By Corollary 2.2, $K e r (^{t} W_{t k}) = {0}$ ⁠. Then $w_{G} = w_{\bar{G}}$ ⁠, so $G = \bar{G}$ ⁠, which is impossible. So there is a $k$ -element subset $K$ of $V$ such that $e ({\bar{G}}_{↾ K}) \neq e (G_{↾ K})$ ⁠.

(2) For $x \in V$ ⁠, $d_{G} (x) + d_{\bar{G}} (x) = v - 1$ ⁠. Since $d_{G} (x) = \frac{v - 1}{2}$ then $d_{G} (x) = d_{\bar{G}} (x)$ ⁠. We have $\sum_{x \in V} d_{G} (x) = 2 e (G)$ and $\sum_{x \in V} d_{\bar{G}} (x) = 2 e (\bar{G})$ ⁠, then $e (G) = e (\bar{G})$ ⁠. Now from $e (\bar{G}) = e (\bar{G} - x) + d_{\bar{G}} (x)$ and $e (G) = e (G - x) + d_{G} (x)$ ⁠, we deduce that $e (\bar{G} - x) = e (G - x)$ ⁠.

(3) For $x \in V$ ⁠, $d_{G} (x) + d_{\bar{G}} (x) = v - 1$ ⁠. Since $2 d_{G} (x) \equiv v - 1 (m o d p)$ then $d_{G} (x) \equiv d_{\bar{G}} (x) (m o d p)$ ⁠. We conclude using similar arguments to those in item (2). □

3.2 Proof of Theorem 1.2

We set t $: =$ 2. We recall the notation $k = {[k_{0}, k_{1}, \dots, k_{k (p)}]}_{p}$ ⁠.

(1) Case 1. $p = 2$ and $k \equiv 2 (m o d 4)$ ⁠.

We have $k_{0} = 0$ ⁠, $k_{1} = 1$ ⁠, $t = {[0,1]}_{2}$ ⁠. Since $k_{0} = t_{0}$ and $k_{1} \geq t_{1} = t_{t (p)}$ then, by Theorem 2.3, $K e r (^{t} W_{t k}) = {0}$ (mod $p$ ⁠).

Case 2. $p \geq 3$ and $k ≢ 0,1 (m o d p)$ ⁠.

We have $k_{0} \geq 2$ ⁠, $t = t_{0} = 2$ ⁠. Since $k_{0} \geq 2 = t_{t (p)}$ then, by Theorem 2.3, $K e r (^{t} W_{t k}) = {0}$ (mod $p$ ⁠).

In the two cases, $K e r (^{t} W_{t k}) = {0}$ (mod $p$ ⁠). Assume that $e ({\bar{G}}_{↾ K}) \equiv e (G_{↾ K}) (m o d p)$ for all $k$ -element subsets $K$ of $V$ ⁠. Then $w_{G} W_{2 k} = w_{\bar{G}} W_{2 k} (m o d p)$ ⁠. As $K e r (^{t} W_{t k}) = {0}$ (mod $p$ ⁠), then $w_{G} = w_{\bar{G}} (m o d p)$ ⁠, so $G = \bar{G}$ ⁠, which is impossible. Then there is a $k$ -element subset $K$ of $V$ such that $e ({\bar{G}}_{↾ K}) ≢ e (G_{↾ K}) (m o d p)$ ⁠.

(2) If $p \geq 3$ then $t = t_{0} = 2 = t_{t (p)}$ ⁠. Since $k \equiv 0 (m o d p)$ then $k_{0} = 0$ ⁠, and thus $k = \sum_{i = t (p) + 1}^{k (p)} k_{i} p^{i}$ ⁠. By Theorem 2.3, ${(1,1, \dots, 1)}$ is a basis of $K e r (^{t} W_{t k})$ ⁠.

If $G$ is the complete graph or the empty graph then $e (G_{↾ K}) \equiv e ({\bar{G}}_{↾ K}) (m o d p)$ ⁠. Indeed, if $G$ is the complete graph then $e (G_{↾ K}) = (\begin{matrix} k \\ 2 \end{matrix})$ ⁠, $e ({\bar{G}}_{↾ K}) = 0$ ⁠. Since $t_{0} = 2 > k_{0} = 0$ then, by Corollary 2.5, $p | (\begin{matrix} k \\ 2 \end{matrix})$ ⁠. So $e (G_{↾ K}) \equiv 0 \equiv e ({\bar{G}}_{↾ K}) (m o d p)$ ⁠. If $G$ is the empty graph, then $e (G_{↾ K}) = 0 \equiv e ({\bar{G}}_{↾ K}) = (\begin{matrix} k \\ 2 \end{matrix}) (m o d p)$ ⁠.

Conversely if $G$ is neither the complete graph nor the empty graph, assume that $e ({\bar{G}}_{↾ K}) \equiv e (G_{↾ K}) (m o d p)$ for all $k$ -element subsets $K$ of $V$ ⁠. Then $w_{G} W_{2 k} = w_{\bar{G}} W_{2 k} (m o d p)$ ⁠. So $w_{G} - w_{\bar{G}} = λ (1, \dots, 1) (m o d p)$ with $λ \in {0,1, - 1}$ ⁠. As $G$ is neither the complete graph nor the empty graph, there are $i, j$ such that $g_{i} = 0$ and $g_{j} = 1$ ⁠, so $g_{i} - \bar{g_{i}} = - 1$ and $g_{j} - \bar{g_{j}} = 1$ ⁠. Then $λ \neq 1$ and $λ \neq - 1$ ⁠. Thus $λ = 0$ ⁠, and $w_{G} = w_{\bar{G}} (m o d p)$ ⁠, so $G = \bar{G}$ ⁠, which is impossible. Then there is a $k$ -element subset $K$ of $V$ such that $e ({\bar{G}}_{↾ K}) ≢ e (G_{↾ K}) (m o d p)$ ⁠. □

3.3 Proof of Theorem 1.3

We need the following lemma.

Lemma 3.1.

Let $G = (V, E)$ be a graph of order $v$ and let $p$ be a prime number, $p \geq 3$ .

Let $k$ be an integer, $2 \leq k \leq v - 2$ ⁠. If $(\begin{matrix} v - 2 \\ k - 2 \end{matrix}) e (G) ≢ (\begin{matrix} v - 2 \\ k - 2 \end{matrix}) e (\bar{G}) (m o d p)$ then there is a $k$ -element subset $K$ of $V$ such that $e (G_{↾ K}) ≢ e ({\bar{G}}_{↾ K}) (m o d p)$ .
If $(v - 2) e (G) ≢ (v - 2) e (\bar{G}) (m o d p)$ then there is $x \in V$ such that $e (G - x) ≢ e (\bar{G} - x) (m o d p)$ .

Proof.

(1) It is an immediate consequence of the following formula
$(\begin{matrix} v - 2 \\ k - 2 \end{matrix}) e (G) = \sum_{\begin{array}{l} K \subset V \\ | K | = k \end{array}} e (G_{↾ k})$
(2) Follows from (1) by taking $k = v - 1$ ⁠. □

Now we prove Theorem 1.3.

(1) Assume that $e (\bar{G} - x) = e (G - x)$ for all $x \in V$ ⁠. From $e (G) = e (G - x) + d_{G} (x)$ ⁠, we obtain $\sum_{x \in V} e (G) = \sum_{x \in V} e (G - x) + \sum_{x \in V} d_{G} (x)$ ⁠. Since $\sum_{x \in V} d_{G} (x) = 2 e (G)$ then $(v - 2) e (G) = \sum_{x \in V} e (G - x)$ ⁠. Similarly, $(v - 2) e (\bar{G}) = \sum_{x \in V} e (\bar{G} - x)$ ⁠. Then $e (G) = e (\bar{G})$ ⁠.

(2) We make the proof by induction on $v$ ⁠. We set $H_{v} : = V$ ⁠. We assume that $H_{i}$ is defined for all $k \leq i \leq v$ ⁠. Let us define $H_{k - 1}$ ⁠. As $e (G_{↾ H_{k}}) \neq e ({\bar{G}}_{↾ H_{k}})$ then by (1), there is $x \in H_{k}$ such that $e (G_{↾ H_{k}} - x) \neq e ({\bar{G}}_{↾ H_{k}} - x)$ ⁠. We set $H_{k - 1} : = H_{k} \ {x}$ ⁠. So $H_{k - 1} \subset H_{k}$ and $e (G_{↾ H_{k - 1}}) \neq e ({\bar{G}}_{↾ H_{k - 1}})$ ⁠.

(3) By applying (1) of Theorem 1.1 for the graph $G$ and $k = v - 2$ we obtain $x \neq y \in V$ such that $e (G - {x, y}) \neq e (\bar{G} - {x, y})$ ⁠. If $v = 4$ we are done. If $v \geq 5$ ⁠, then $v - 2 \geq 3$ and here we conclude using (2).

(4) By induction on $v$ ⁠. Since $e (G) ≢ e (\bar{G}) (m o d p)$ and $p > v - 2$ then $(v - 2) e (G) ≢ (v - 2) e (\bar{G}) (m o d p)$ ⁠. By (2) of Lemma 3.1, there is $x \in V$ such that $e (\bar{G} - x) ≢ e (G - x) (m o d p)$ ⁠. We conclude by using the induction hypothesis. □

The publisher wishes to inform readers that the article “On the number of edges of a graph and its complement” was originally published by the previous publisher of the Arab Journal of Mathematical Sciences and the pagination of this article has been subsequently changed. There has been no change to the content of the article. This change was necessary for the journal to transition from the previous publisher to the new one. The publisher sincerely apologises for any inconvenience caused. To access and cite this article, please use Dammak, J., Lopez, G., Kaddour, H. S. (2019), “On the number of edges of a graph and its complement”, Arab Journal of Mathematical Sciences, Vol. 27 No. 1, pp. 15-19. The original publication date for this paper was 29/05/2019.

References

[1]

A.

Ben Amira

,

J.

Dammak

,

H.

Si Kaddour

,

On a generalization of Kelly’s combinatorial lemma

,

Turk. J. Math.

36

(

2014

)

949

–

964

.

Google Scholar

[2]

J.A.

Bondy

,

Basic graph theory: paths and circuits

, in:

R.L.

Graham

,

M.

Grötschel

,

L.

Lovász

(Eds.),

HandBook of Combinatorics

,

Vol. 1

,

North-Holland

,

1995

, pp.

3

–

110

.

Google Scholar

[3]

N.J.

Fine

,

Binomial coefficients modulo a prime

,

Amer. Math. Monthly

54

(

(10) Part 1

) (

1947

)

589

–

592

.

Google Scholar

[4]

D.H.

Gottlieb

,

A certain class of incidence matrices

,

Proc. Amer. Math. Soc.

17

(

1966

)

1233

–

1237

.

Google Scholar

Crossref

[5]

W.M.

Kantor

,

On incidence matrices of finite projective and affine spaces

,

Math. Z.

124

(

1972

)

315

–

318

.

Google Scholar

Crossref

[6]

P.J.

Kelly

,

A congruence theorem for trees

,

Pac. J. Math.

7

(

1957

)

961

–

968

.

Google Scholar

Crossref

[7]

M.

Pouzet

,

Application d’une propriété combinatoire des parties d’un ensemble aux groupes et aux relations

,

Math. Z.

150

(

1976

)

117

–

134

.

Google Scholar

Crossref

2019

Jamel Dammak, Gerard Lopez and Hamza Si Kaddour

Published in the Arab Journal of Mathematical Sciences. Published by Emerald Publishing Limited. This article is published under the Creative Commons Attribution (CC BY 4.0) license. Anyone may reproduce, distribute, translate and create derivative works of this article (for both commercial and non-commercial purposes), subject to full attribution to the original publication and authors. The full terms of this license may be seen at http://creativecommons.org/licences/by/4.0/legalcode

On the number of edges of a graph and its complement

1. Introduction

2. Incidence matrices

3. Proofs of main results

3.1 Proof of Theorem 1.1

3.2 Proof of Theorem 1.2

3.3 Proof of Theorem 1.3

References

Email Alerts

Cited By

On the number of edges of a graph and its complement Open Access

1. Introduction

2. Incidence matrices

3. Proofs of main results

3.1 Proof of Theorem 1.1

3.2 Proof of Theorem 1.2

3.3 Proof of Theorem 1.3

References

Email Alerts

Suggested Reading

Related Chapters

Recommended for you

Cited By

Sharing Unavailable

On the number of edges of a graph and its complement