# Equality of graphs up to complementation

Jamel Dammak, Gérard Lopez, Hamza Si Kaddour

► To cite this version:

Jamel Dammak, Gérard Lopez, Hamza Si Kaddour. Equality of graphs up to complementation. Arabian Journal of Mathematics, 2020, 10 (1), pp.59-66. 10.1007/s40065-020-00297-8. hal-04761117

HAL Id: hal-04761117

https://hal.science/hal-04761117v1

Submitted on 14 Mar 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
Jamel Dammak · Gérard Lopez · Hamza Si Kaddour

# Equality of graphs up to complementation

Received: 15 June 2019 / Accepted: 21 September 2020 / Published online: 2 November 2020
© The Author(s) 2020

**Abstract** We prove the following: Let $G$ and $G'$ be two graphs on the same set $V$ of $v$ vertices, and let $k$ be an integer, $4 \le k \le v-4$. If for all $k$-element subsets $K$ of $V$, the induced subgraphs $G_{\uparrow K}$ and $G'_{\uparrow K}$ have the same numbers of 3-homogeneous subsets, the same numbers of $P_4$'s, and the same numbers of claws or co-claws, then $G'$ is equal to $G$ or to the complement $\bar{G}$ of $G$. We give also a similar result whenever the same numbers are modulo a prime.

**Mathematics Subject Classification** 05C50 · 05C60

## 1 Introduction and main results

Our notations and terminology follow [2]. A *symmetric graph* (or more simply *graph*) is an ordered pair $G := (V, \mathcal{E})$, where $\mathcal{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 $\mathcal{E}$ its *edges*. If $K$ is a subset of $V$, the *restriction* of $G$ to $K$, also called the *induced graph* on $K$ is the graph $G_{\uparrow K} := (K, [K]^2 \cap \mathcal{E})$. The *complement* of $G$ is the graph $\bar{G} := (V, [V]^2 \setminus \mathcal{E})$. We denote by $V(G)$ the vertex set of a graph $G$, by $E(G)$ its edge set and by $e(G) := |E(G)|$ the number of edges. Let $G := (V, E)$ be a graph. A 3-element subset $T$ of $V$ such that all pairs belong to $E(G)$ is a *triangle* of $G$. A 3-element subset of $V$ which is a triangle of $G$ or of $\bar{G}$ is a *3-homogeneous subset* of $G$. We denote by $K_3$ the complete graph on 3 vertices and by $K_{1,3}$ the graph made of a vertex linked to a $\bar{K}_3$. The graph $K_{1,3}$ is called a *claw*, the graph $\bar{K}_{1,3}$ a *co-claw*. For these graphs, see Fig. 1.

In memory of Gérard Lopez with all our affection and admiration. Gérard Lopez died on April 8, 2019; this work was at the end of writing.

Deceased: Gérard Lopez

J. Dammak
Department of Mathematics, Faculty of Sciences of Sfax, B.P. 1171, 3000 Sfax, Tunisia
E-mail: jdammak@yahoo.fr

G. Lopez
Institut de Mathématiques de Luminy, CNRS-UPR 9016,163 avenue de Luminy, case 907, 13288 Marseille cedex 9, France
E-mail: gerardlopez@free.fr

H. Si Kaddour (✉)
Université de Lyon, Université Claude Bernard Lyon 1, CNRS UMR 5208, Institut Camille Jordan, 43 blvd. du 11 novembre 1918, 69622 Villeurbanne cedex, France
E-mail: sikaddour@univ-lyon1.fr
<figure><img src="image_2.png" /><figcaption>Fig. 1 $K_3, K_{1,3}, \overline{K_{1,3}}, P_4$</figcaption></figure>

Given two graphs $G := (V, E)$ and $G' := (V', E')$. A bijection $f$ from $V$ onto $V'$ is an isomorphism from $G$ onto $G'$ provided that for any $x, y \in V$, $\{x, y\} \in E$ if and only if $\{f(x), f(y)\} \in E'$. The graphs $G$ and $G'$ are isomorphic, which is denoted by $G \simeq G'$, if there exists an isomorphism from one onto the other, otherwise $G \not\simeq G'$.

Let $G, G'$ be two graphs on the same vertex set $V$. We say that $G$ and $G'$ are equal up to complementation if $G' = G$ or $G' = \bar{G}$. If $G'$ has the same number of edges as $G$ or $\bar{G}$, we say that $G$ and $G'$ have the same number of edges up to complementation. We say that $G$ and $G'$ are isomorphic up to complementation if $G'$ is isomorphic to $G$ or to $\bar{G}$. Let $k$ be a non-negative integer, $G$ and $G'$ are $k$-hypomorphic up to complementation if for every $k$-element subset $K$ of $V$, the induced subgraphs $G_{\uparrow K}$ and $G'_{\uparrow K}$ are isomorphic up to complementation.

Ulam's Reconstruction Conjecture [3,12] asserts that two graphs $G$ and $G'$ on the same finite set $V$ of $v$ vertices, $v \ge 3$, are isomorphic provided that the restrictions $G_{\uparrow K}$ and $G'_{\uparrow K}$ of $G$ and $G'$ to the $(v-1)$-element subsets $K$ of $V$ are isomorphic. If this latter condition holds for the $k$-element subsets of $V$ for some $k, 2 \le k \le v-2$, then $G' = G$. This conclusion does not require the isomorphy of $G_{\uparrow K}$ and $G'_{\uparrow K}$, but only requires that $G_{\uparrow K}$ and $G'_{\uparrow K}$ have the same number of edges for all $k$-element subsets $K$ of $V$. In [4], a work has been done where the conditions are $G'_{\uparrow K}$ and $G_{\uparrow K}$ are isomorphic up to complementation for all $k$-element subsets $K$ of $V$, or $G'_{\uparrow K}$ and $G_{\uparrow K}$ have the same number of edges up to complementation for all $k$-element subsets $K$ of $V$. Let $v$ be a non negative integer and $\vartheta(v) := 4l$ if $v \in \{4l+2, 4l+3\}$, $\vartheta(v) := 4l-3$ if $v \in \{4l, 4l+1\}$. The following theorems was obtained in [4].

**Theorem 1.1** [4] Let $v, k$ be two integers with $4 \le k \le \vartheta(v)$. Then, for every pair of graphs $G$ and $G'$ on the same set $V$ of $v$ vertices, if $G_{\uparrow K}$ and $G'_{\uparrow K}$ have the same number of edges, up to complementation, and the same number of 3-homogeneous subsets, for all $k$-element subsets $K$ of $V$, then $G' = G$ or $G' = \bar{G}$.

**Theorem 1.2** [4] Let $k$ be an integer, $4 \le k \le v-2$, $k \equiv 0 \pmod 4$. Let $G$ and $G'$ be two graphs on the same set $V$ of $v$ vertices.

We assume that $e(G_{\uparrow K})$ has the same parity as $e(G'_{\uparrow K})$ for all $k$-element subsets $K$ of $V$.
Then $G' = G$ or $G' = \bar{G}$.

It is also shown in [4] that two graphs $G$ and $G'$ on the same set of $v$ vertices are equal up to complementation whenever they are $k$-hypomorphic up to complementation and $4 \le k \le v-4$ (for the case $k = v-3$, the conclusion obtained is $G' \simeq G$ or $G' \simeq \bar{G}$ [5]). Later, an extension of this result was obtained for uniform hypergraphs [9].

**Theorem 1.3** [9] Let $h$ be a non-negative integer. There are two non-negative integers $k$ and $t$, $k \le t$ such that two $h$-uniform hypergraphs $\mathcal{H}$ and $\mathcal{H}'$ on the same set $V$ of vertices, $|V| \ge t$, are equal up to complementation whenever $\mathcal{H}$ and $\mathcal{H}'$ are $k$-hypomorphic up to complementation.

In this paper, we look for similar results on graphs if the conditions on the restrictions $G_{\uparrow K}$ and $G'_{\uparrow K}$ are that they have the same numbers of 3-homogeneous subsets, the same numbers of $P_4$'s, and the same numbers of claws or co-claws, we obtain Theorem 1.4. Whenever the same numbers (cited above) are modulo a prime, we obtain Theorem 1.7. This last theorem is a consequence of Theorem 1.4 and Proposition 4.3 which is inspired by a result of Pouzet on monomorphic relations (Proposition 4.2).

Let $G := (V, E)$ be a graph. We set:

$$H^{(3)}(G) := \{\{a, b, c\} \subset V : G_{\uparrow \{a,b,c\}} \simeq K_3 \text{ or } G_{\uparrow \{a,b,c\}} \simeq \overline{K_3}\}$$

$$P^{(4)}(G) := \{\{a, b, c, d\} \subset V : G_{\uparrow \{a,b,c,d\}} \simeq P_4\}$$

$$S^{(4)}(G) := \{\{a, b, c, d\} \subset V : G_{\uparrow \{a,b,c,d\}} \simeq K_{1,3} \text{ or } G_{\uparrow \{a,b,c,d\}} \simeq \overline{K_{1,3}}\}$$

$$h^{(3)}(G) := |H^{(3)}(G)|, p^{(4)}(G) := |P^{(4)}(G)|, s^{(4)}(G) := |S^{(4)}(G)|.$$

Our first result is:

<figure><img src="image_3.png" /></figure>
**Theorem 1.4** Let $G, G'$ be two graphs on the same finite set $V$ of $v \ge 4$ vertices.

(1) If $H^{(3)}(G) = H^{(3)}(G')$, $P^{(4)}(G) = P^{(4)}(G')$ and $S^{(4)}(G) = S^{(4)}(G')$, then $G' = G$ or $G' = \bar{G}$.

(2) Let $k$ be an integer, $4 \le k \le v-4$.

If $h^{(3)}(G_{\uparrow K}) = h^{(3)}(G'_{\uparrow K})$, $p^{(4)}(G_{\uparrow K}) = p^{(4)}(G'_{\uparrow K})$ and $s^{(4)}(G_{\uparrow K}) = s^{(4)}(G'_{\uparrow K})$ for all $k$-element subsets $K$ of $V$, then $G' = G$ or $G' = \bar{G}$.

The proof of Theorem 1.4 will be given in Sect. 3. The following propositions show that Theorem 1.4 is optimal.

**Proposition 1.5** For every integer $v \ge 4$ and every integer $k$, $4 \le k \le v$, there are two graphs $G$ and $G'$ on the same set of $v$ vertices, nonisomorphic up to complementation, satisfying $p^{(4)}(G_{\uparrow K}) = p^{(4)}(G'_{\uparrow K})$ and $s^{(4)}(G_{\uparrow K}) = s^{(4)}(G'_{\uparrow K})$ for all $k$-element subsets $K$ of $V$.

*Proof* Let $V := \{1, 2, \dots, v\}$ with $v \ge 4$. Let $G$ and $G'$ be two graphs on the same vertex set $V$ defined by $G_{\uparrow \{2,3,\dots,v\}}$ and $G'_{\uparrow \{2,3,\dots,v\}}$ are complete graphs, $\{1, x\} \in E(G)$ if $x \ne 2$; $\{1, x\} \in E(G')$ if $x \notin \{2, 3\}$. Clearly $p^{(4)}(G_{\uparrow K}) = p^{(4)}(G'_{\uparrow K}) = 0$ and $s^{(4)}(G_{\uparrow K}) = s^{(4)}(G'_{\uparrow K}) = 0$ for all $k$-element subsets $K$ of $V$. But $G$ and $G'$ are not isomorphic up to complementation. $\square$

**Proposition 1.6** For every integer $n \ge 4$, there are two graphs $G$ and $G'$ on the same set of $2n$ vertices, nonisomorphic up to complementation, satisfying $h^{(3)}(G) = h^{(3)}(G')$ and $p^{(4)}(G) \ne p^{(4)}(G')$.

*Proof* We set $G := M_{2n}$ and $G' := M'_{2n}$ (For the definition of the graphs $M_{2n}$ and $M'_{2n}$, see Sect. 3, Fig. 3). Clearly, $G$ and $G'$ are not isomorphic up to complementation. We have $h^{(3)}(G) = h^{(3)}(G')$, but $p^{(4)}(G) \ne p^{(4)}(G')$ since $p^{(4)}(G) = n(n-1)(n-2)$ and $p^{(4)}(G') = (n-1)(n-2)^2 + (n-1)^2$. $\square$

Let $k, p$ be positive integers, the decomposition of $k = \sum_{i=0}^{k(p)} k_i p^i$ in the basis $p$ is also denoted $[k_0, k_1, \dots, k_{k(p)}]_p$ where $k_{k(p)} \ne 0$ if and only if $k \ne 0$.

As an application of Theorem 1.4, our second result is:

**Theorem 1.7** Let $G, G'$ be two graphs on the same set $V$ of $v$ vertices. Let $p$ be a prime number, $p \ge 5$ and $k = [k_0, k_1, \dots, k_{k(p)}]_p$ be an integer, $4 \le k \le v-4$; ($k_0 = 0$ or $k_0 \ge 4$).

If $h^{(3)}(G_{\uparrow K}) = h^{(3)}(G'_{\uparrow K}) (\text{mod } p)$, $p^{(4)}(G_{\uparrow K}) = p^{(4)}(G'_{\uparrow K}) (\text{mod } p)$ and $s^{(4)}(G_{\uparrow K}) = s^{(4)}(G'_{\uparrow K}) (\text{mod } p)$ for all $k$-element subsets $K$ of $V$, then $G' = G$ or $G' = \bar{G}$.

The proof of Theorem 1.7 will be given in Sect. 4.

## 2 Sketch of the proofs of Theorems 1.4 and 1.7

Let $G, G'$ be two graphs on the same vertex set $V$. The Boolean sum $G \oplus G'$ of $G$ and $G'$ is the graph $U$ on $V$ whose edges are pairs $e$ of vertices such that $e \in E(G)$ if and only if $e \notin E(G')$. Indeed, $G' = G$ or $G' = \bar{G}$ amounts to the fact that $U$ is either the empty graph or the complete graph. The intersection graph of $G$ and $G'$ is the graph $G \cap G' := (V, E(G) \cap E(G'))$.

**Observation 2.1** [5] Let $G$ and $G'$ be two graphs on the same finite set $V$ of $v$ vertices, and let $U := G \oplus G'$. Then

(1) $e(U) = e(G) + e(G') - 2e(G \cap G')$.

(2) $e(G)$ and $e(G')$ have the same parity if and only if $e(U)$ is even.

To prove (1) of Theorem 1.4, we consider $U := G \oplus G'$. From Theorem 1.2, it is sufficient to prove that $e(G_{\uparrow X})$ has the same parity as $e(G'_{\uparrow X})$ for all $4$-element subsets $X$ of $V$ that is, from Observation 2.1, $e(U_{\uparrow X})$ is even for all $4$-element subsets $X$ of $V$. For this we proceed by contradiction, assuming that $e(U_{\uparrow X})$ is odd. As $H^{(3)}(G) = H^{(3)}(G')$, Theorem 3.1 says that $U_{\uparrow X}$ is a path of length 1 or 3. If the length is one, we study two cases. If the length is 3, we conclude using Theorem 3.2.

To prove item (2), and also Theorem 1.7, we will prove that item (1) of Theorem 1.4 holds. For this, we will use linear algebra. The incidence matrix $W_{t_k}(v)$ used by Wilson [13], or more simply $W_{t_k}$, is defined as follows : Let $V$ be a finite set, with $v$ elements. Given non-negative integers $t \le k \le v$, let $W_{t_k}$ be the $\binom{v}{t}$

<figure><img src="image_4.png" /></figure>
by $\binom{v}{k}$ 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 if $T \subseteq K$ and is 0 otherwise. The matrix transpose of $W_{t,k}$ is denoted $^tW_{t,k}$. We denote by $rank_Q W_{t,k}$, the rank of $W_{t,k}$ over the field $\mathbb{Q}$. Whenever $p$ is a prime, we denote by $rank_p W_{t,k}$, the rank of $W_{t,k}$ over the field $\mathbb{F}_p$, and by $Ker_p(^tW_{t,k})$ the kernel of $^tW_{t,k}$ in $\mathbb{F}_p$.

First, $rank_Q W_{t,k}$ is given by Theorem 2.2 due to Gottlieb [7].

**Theorem 2.2** [7] For $t \le \min(k, v-k)$, the rank of $W_{t,k}$ over the field $\mathbb{Q}$ of rational numbers is $\binom{v}{t}$ and thus $Ker(^tW_{t,k}) = \{0\}$.

Let $G := (V, E)$ be a graph with $v$ vertices, $v \ge 6$. Let $t \in \{3, 4\}$, and $k$ be an integer, $k \le v$ and $t \le \min(k, v-k)$.

Let $T_1, T_2, \dots, T_{\binom{v}{t}}$ be an enumeration of the $t$-element subsets of $V$.

Let $K_1, K_2, \dots, K_{\binom{v}{t}}$ be an enumeration of the $k$-element subsets of $V$.

We set:

$$w_G^h := (g_1^h, g_2^h, \dots, g_{\binom{v}{3}}^h) \text{ where } g_i^h = 1 \text{ if } T_i \in H^{(3)}(G), 0 \text{ otherwise.}$$

$$w_G^p := (g_1^p, g_2^p, \dots, g_{\binom{v}{4}}^p) \text{ where } g_i^p = 1 \text{ if } T_i \in P^{(4)}(G), 0 \text{ otherwise.}$$

$$w_G^s := (g_1^s, g_2^s, \dots, g_{\binom{v}{4}}^s) \text{ where } g_i^s = 1 \text{ if } T_i \in S^{(4)}(G), 0 \text{ otherwise.}$$

We have:

$$w_G^h W_{3,k} = (h^3(G_{\uparrow K_1}), h^3(G_{\uparrow K_2}), \dots, h^3(G_{\uparrow K_{\binom{v}{k}}})),$$

$$w_G^p W_{4,k} = (p^{(4)}(G_{\uparrow K_1}), p^{(4)}(G_{\uparrow K_2}), \dots, p^{(4)}(G_{\uparrow K_{\binom{v}{k}}}))$$

$$w_G^s W_{4,k} = (s^{(4)}(G_{\uparrow K_1}), s^{(4)}(G_{\uparrow K_2}), \dots, s^{(4)}(G_{\uparrow K_{\binom{v}{k}}}))$$

**Observation 2.3** Let $G$ and $G'$ be two graphs on the same finite set $V$ of $v$ vertices.

(1) If $h^{(3)}(G_{\uparrow K_i}) = h^{(3)}(G'_{\uparrow K_i})$ (resp. $h^{(3)}(G_{\uparrow K_i}) \equiv h^{(3)}(G'_{\uparrow K_i}) \pmod p$) for all $i \in \{1, 2, \dots, \binom{v}{k}\}$, then $w_G^h - w_{G'}^h \in Ker_Q(^tW_{3,k})$ (resp. $w_G^h - w_{G'}^h \in Ker_p(^tW_{3,k})$).

(2) If $p^{(4)}(G_{\uparrow K_i}) = p^{(4)}(G'_{\uparrow K_i})$ (resp. $p^{(4)}(G_{\uparrow K_i}) \equiv p^{(4)}(G'_{\uparrow K_i}) \pmod p$) for all $i \in \{1, 2, \dots, \binom{v}{k}\}$, then $w_G^p - w_{G'}^p \in Ker_Q(^tW_{4,k})$ (resp. $w_G^p - w_{G'}^p \in Ker_p(^tW_{4,k})$).

(3) If $s^{(4)}(G_{\uparrow K_i}) = s^{(4)}(G'_{\uparrow K_i})$ (resp. $s^{(4)}(G_{\uparrow K_i}) \equiv s^{(4)}(G'_{\uparrow K_i}) \pmod p$) for all $i \in \{1, 2, \dots, \binom{v}{k}\}$, then $w_G^s - w_{G'}^s \in Ker_Q(^tW_{4,k})$ (resp. $w_G^s - w_{G'}^s \in Ker_p(^tW_{4,k})$).

Now for the end of the proof of item (2), from Observation 2.3, $w_G^h - w_{G'}^h \in Ker_Q(^tW_{3,k})$. From Theorem 2.2, $Ker_Q(^tW_{3,k}) = \{0\}$, then $w_G^h = w_{G'}^h$. Thus, $H^{(3)}(G) = H^{(3)}(G')$. For the other parameters, we do the same. Thus, we get the hypotheses of item (1).

For Theorem 1.7, there are two cases according to the value of $k_0$. If $k_0 \ge 4$, we proceed as above. If $k_0 = 0$, we use Theorem 4.1 which gives the dimension and a basis of $Ker_p(^tW_{t,k})$.

### 3 Proof of Theorem 1.4

A description of the Boolean sum $G \oplus G'$, of graphs $G$ and $G'$ having the same 3-element homogeneous subsets, is given by Theorem 3.1 below.

We denote by $P_9$ the Paley graph on 9 vertices (cf. Fig. 2). Note that $P_9$ is isomorphic to its complement $\overline{P_9}$.

**Theorem 3.1** [10] Let $U$ be a graph. The following properties are equivalent:

(1) There are two graphs $G$ and $G'$ having the same 3-element homogeneous subsets such that $U := G \oplus G'$;

(2) Either (i) $U$ is an induced subgraph of $P_9$, or (ii) the connected components of $U$, or of its complement $\overline{U}$, are cycles of even length or paths.

<figure><img src="image_5.png" /></figure>
<figure><img src="image_6.png" /><figcaption>Fig. 2 P9</figcaption></figure>

<figure><img src="image_7.png" /><figcaption>Fig. 3 $M_n, M'_n, M''_n, D_4, D'_4$</figcaption></figure>

For graphs $G$ and $G'$ having the same 3-element homogeneous subsets, Theorem 3.2 below gives the form of their restrictions on a connected component of $G+G'$.

**Theorem 3.2** [5] Let $G$ and $G'$ be two graphs on the same vertex set $V$ and $U := G+G'$. We assume $H^{(3)}(G) = H^{(3)}(G')$ and $U$ not connected. If $C$ is a connected component of $U$ of cardinality $n$, then the pair $\{G \upharpoonright_V C, G' \upharpoonright_{V(C)}\}$ is one of the following:

(1) $\{M_n, M'_n\}, \{\overline{M}_n, \overline{M}'_n\}$, if $C$ is a path.

(2) $\{M_n, M''_n\}, \{\overline{M}_n, \overline{M}''_n\}, \{D_4, D'_4\}, \{\overline{D}_4, \overline{D}'_4\}$, if $C$ is a cycle.

The graphs mentioned in the conclusion of Theorem 3.2 are defined as follows (see Fig. 3).

Let $n \ge 2$. Let $X_n$ be an $n$-element set, $v_0, \dots, v_{n-1}$ be an enumeration of $X_n$, $X_n^0 := \{v_i \in X_n : i \equiv 0 \pmod 2\}$ and $X_n^1 := X_n \setminus X_n^0$. Set $R_n := [X_n^0]^2 \cup [X_n^1]^2$, $S_n := \{\{v_{2i}, v_{2i+1}\} : 2i + 1 < n\}$, $S'_n := \{\{v_{2i+1}, v_{2i+2}\} : 2i + 2 < n\}$. Let $M_n$ and $M'_n$ be the graphs with vertex set $X_n$ and edge sets $E(M_n) := R_n \cup S_n$ and $E(M'_n) := R_n \cup S'_n$, respectively. Let $M''_n := (X_n, R_n \cup S'_n \cup \{\{v_0, v_{n-1}\}\})$ for $n$ even, $n \ge 4$. Finally, let $D_4 := (X_4, \{\{v_0, v_1\}, \{v_0, v_2\}, \{v_2, v_3\}\})$ and $D'_4 := (X_4, \{\{v_0, v_2\}, \{v_0, v_3\}, \{v_1, v_2\}\})$.

Let $G = (V, E)$ be a graph. For $x \neq y \in V$, $x \sim_G y$ means $\{x, y\} \in E$, $x \not\sim_G y$ means $\{x, y\} \notin E$. For $X, Y \subseteq V$, $X \sim_G Y$ signifies that for every $x \in X$ and $y \in Y$, $x \sim_G y$. Similarly, $X \not\sim_G Y$ signifies that for every $x \in X$ and $y \in Y$, $x \not\sim_G y$. Whenever $X = \{x\}$, $X \sim_G Y$ and $X \not\sim_G Y$ are, respectively, denoted $x \sim_G Y$ and $x \not\sim_G Y$.

Now we prove Theorem 1.4.

<figure><img src="image_8.png" /></figure>
(1) Let $U := G \cup G'$. Using Theorem 1.2, it is sufficient to prove that $e(G_{\uparrow X})$ has the same parity as $e(G'_{\uparrow X})$ for all 4-element subsets $X$ of $V$ that is, from Observation 2.1, $e(U_{\uparrow X})$ is even for all 4-element subsets $X$ of $V$.

Let $X := \{v_0, v_1, v_2, v_3\}$ be a subset of $V$. By contradiction, we assume that $e(U_{\uparrow X})$ is odd, then $e(U_{\uparrow X}) \in \{1, 3, 5\}$. As $H^{(3)}(G) = H^{(3)}(G')$ then, by Theorem 3.1, $E(U_{\uparrow X}) = \{\{v_0, v_1\}, \{v_1, v_2\}, \{v_2, v_3\}\}$ or $\{\{v_0, v_1\}\}$.

* If $E(U_{\uparrow X}) = \{\{v_0, v_1\}, \{v_1, v_2\}, \{v_2, v_3\}\}$, we apply (1) of Theorem 3.2. So $\{G_{\uparrow X}, G'_{\uparrow X}\} = \{M_4, M'_4\}$ or $\overline{M_4, M'_4}$. We get a contradiction with $P^{(4)}(G) = P^{(4)}(G')$ since $M_4 \notin P^{(4)}(G) \cup P^{(4)}(G')$ and $M'_4 \in P^{(4)}(G) \cap P^{(4)}(G')$.

* If $E(U_{\uparrow X}) = \{\{v_0, v_1\}\}$, we can suppose $v_0 \sim_G v_1$ and $v_0 \sim_{G'} v_1$. Without loss of generality, we assume $v_0 \sim_G v_2$. As $v_0 \sim_U v_2$, $v_0 \sim_{G'} v_2$. We have $v_0 \sim_G \{v_1, v_2\}$, $v_0 \sim_{G'} v_1$ and $v_0 \sim_{G'} v_2$. As $H^3(G) = H^3(G')$, $v_2 \sim_G v_1$. Since $v_2 \sim_U v_1$ then $v_2 \sim_{G'} v_1$.

Case 1. $v_0 \sim_G v_3$. Since $v_0 \sim_U v_3$ then $v_0 \sim_{G'} v_3$. Consider $\{v_0, v_1, v_3\}$, as $H^{(3)}(G) = H^{(3)}(G')$ we have $v_1 \sim_G v_3$, thus $v_1 \sim_{G'} v_3$.

If $v_2 \sim_G v_3$, then $v_2 \sim_{G'} v_3$. So $\{v_0, v_1, v_2, v_3\} \in S^{(4)}(G)$ and $\{v_0, v_1, v_2, v_3\} \notin S^{(4)}(G')$. That contradicts $S^{(4)}(G) = S^{(4)}(G')$. If $v_2 \sim_G v_3$, then $v_2 \sim_{G'} v_3$. So $\{v_0, v_1, v_2, v_3\} \in S^{(4)}(G')$ and $\{v_0, v_1, v_2, v_3\} \notin S^{(4)}(G)$. That contradicts $S^{(4)}(G) = S^{(4)}(G')$.

Case 2. $v_0 \sim_G v_3$. Since $v_0 \sim_U v_3$ then $v_0 \sim_{G'} v_3$. Consider $\{v_0, v_1, v_3\}$, as $H^{(3)}(G) = H^{(3)}(G')$ we have $v_1 \sim_{G'} v_3$, thus $v_1 \sim_G v_3$.

If $v_2 \sim_G v_3$, then $v_2 \sim_{G'} v_3$. Then $\{v_0, v_1, v_2, v_3\} \in P^{(4)}(G)$ and $\{v_0, v_1, v_2, v_3\} \notin P^{(4)}(G')$. That contradicts $P^{(4)}(G) = P^{(4)}(G')$. If $v_2 \sim_G v_3$, then $v_2 \sim_{G'} v_3$. Then $\{v_0, v_1, v_2, v_3\} \notin P^{(4)}(G)$ and $\{v_0, v_1, v_2, v_3\} \in P^{(4)}(G')$. That contradicts $P^{(4)}(G) = P^{(4)}(G')$.

(2) We will prove $H^{(3)}(G) = H^{(3)}(G')$, $P^{(4)}(G) = P^{(4)}(G')$, $S^{(4)}(G) = S^{(4)}(G')$ and conclude using (1).
From Observation 2.3, $w_G^h - w_{G'}^h \in Ker_{\mathbb{Q}}(^t W_{3k})$. From Theorem 2.2, $Ker_{\mathbb{Q}}(^t W_{3k}) = \{0\}$, then $w_G^h = w_{G'}^h$. Thus $H^{(3)}(G) = H^{(3)}(G')$.

From Observation 2.3, $w_G^p - w_{G'}^p \in Ker_{\mathbb{Q}}(^t W_{4k})$ and $w_G^s - w_{G'}^s \in Ker_{\mathbb{Q}}(^t W_{4k})$. From Theorem 2.2, $Ker_{\mathbb{Q}}(^t W_{4k}) = \{0\}$, then $w_G^p = w_{G'}^p$ and $w_G^s = w_{G'}^s$. Thus $P^{(4)}(G) = P^{(4)}(G')$ and $S^{(4)}(G) = S^{(4)}(G')$.

□

**4 Proof of Theorem 1.7**

The following result is one of the keys to our proof.

**Theorem 4.1** [1] Let $p$ be a prime number. Let $v, t$ and $k$ be non-negative integers, $k \le v, k = [k_0, k_1, \dots, k_{t(p)}]_p$, $t = [t_0, t_1, \dots, t_{t(p)}]_p$, $t \le \min(k, v-k)$. We have:

(1) $k_j = t_j$ for all $j < t(p)$ and $k_{t(p)} \ge t_{t(p)}$ if and only if $Ker_p(^t W_{t_k}) = \{0\}$.

(2) $t = t_{t(p)} p^{t(p)}$ and $k = \sum_{i=t(p)+1}^{k(p)} k_i p^i$ if and only if $dim Ker_p(^t W_{t_k}) = 1$ and $\{(1, 1, \dots, 1)\}$ is a basis of $Ker_p(^t W_{t_k})$.

Let $k \ge 1$ be an integer and $G$ be a graph. We say that $G$ is *k-monomorphic* (resp. *k-monomorphic up to complementation*) if $G_{\uparrow X} \simeq G_{\uparrow Y}$ (resp. $G_{\uparrow X} \simeq G_{\uparrow Y}$ or $G_{\uparrow X} \simeq \overline{G}_{\uparrow Y}$) for all $k$-element subsets $X$ and $Y$ of $V$. The notion of monomorphy was introduced by Fraïssé [6].

The following result on monomorphy, due to Pouzet, is very useful since it is the origin of Proposition 4.3, which is a key in the proof of Theorem 1.7.

**Proposition 4.2** [8] Let $v, t, k$ be integers, $t \le \min(k, v-k)$ and $G$ be a graph on a set $V$ of $v$ vertices. If $G$ is $k$-monomorphic then $G$ is $t$-monomorphic.

We give a similar result (Proposition 4.3) in the case of the monomorphy up to complementation.

**Proposition 4.3** Let $v, t, k$ be integers, $t \le \min(k, v-k)$ and $G$ be a graph on a set $V$ of $v$ vertices. If $G$ is $k$-monomorphic up to complementation then $G$ is $t$-monomorphic up to complementation.

*Proof* Let $T_1, T_2, \dots, T_{\binom{t}{2}}$ be the $t$-element subsets of $V$, and $K_1, K_2, \dots, K_{\binom{t}{k}}$ be the $k$-element subsets of $V$. Let $H := G_{\uparrow T_1}$. Set $Isc(H, G) := \{L \subseteq V : G_{\uparrow L} \simeq H \text{ or } G_{\uparrow L} \simeq \overline{H}\}$ and $w_{H,G}$ the row vector indexed by the $t$-element subsets $T_1, T_2, \dots, T_{\binom{t}{2}}$ of $V$ whose coefficient of $T_i$ is 1 if $T_i \in Isc(H, G)$ and 0 otherwise.

<figure><img src="image_9.png" /></figure>

<figure><img src="image_10.png" /></figure>
We have $w_{H,G}W_t k = (\alpha_1, \alpha_2, \dots, \alpha_{\binom{k}{t}})$ where

$$ \alpha_j := \left| \{ T_i : T_i \subseteq K_j, 1 \le i \le \binom{v}{t}, T_i \in \mathrm{Isc}(H, G) \} \right|. $$

Since $G$ is $k$-monomorphic up to complementation, $\alpha_1 = \alpha_2 = \dots = \alpha_{\binom{v}{t}}$. Thus $w_{H,G}W_t k = \alpha_1(1, 1, \dots, 1)$. Now $(1, 1, \dots, 1)W_t k = (\binom{k}{t}, \binom{k}{t}, \dots, \binom{k}{t}) = \binom{k}{t}(1, 1, \dots, 1)$. It follows that $\binom{k}{t}w_{H,G}W_t k = \alpha_1(1, 1, \dots, 1)W_t k$. From Theorem 2.2, $\mathrm{Ker}_{\mathbb{Q}}(tW_t k) = \{0\}$. Thus $\binom{k}{t}w_{H,G} = \alpha_1(1, 1, \dots, 1)$. Since $H = G|_{T_1}$, then $w_{H,G} \ne (0, 0, \dots, 0)$, this implies $\alpha_1 \ne 0$. Then from $w_{H,G} = \frac{\alpha_1}{\binom{k}{t}}(1, 1, \dots, 1)$, we deduce that $w_{H,G} = (1, 1, \dots, 1)$. So $T_i \in \mathrm{Isc}(H, G)$ for all $i \in \{1, 2, \dots, \binom{v}{t}\}$. Thus $G$ is $t$-monomorphic up to complementation. $\square$

Now we prove Theorem 1.7.

We have $w_G^h W_3 k = w_{G'}^h W_3 k$, $w_G^p W_4 k = w_{G'}^p W_4 k$ and $w_G^s W_4 k = w_{G'}^s W_4 k$.

By Theorem 1.4, it is sufficient to prove that $H^{(3)}(G) = H^{(3)}(G')$, $P^{(4)}(G) = P^{(4)}(G')$ and $S^{(4)}(G) = S^{(4)}(G')$. Let $t \in \{3, 4\}$. According to the value of $k_0$, we have two cases.

Case 1. $k_0 \ge 4$. As $t \in \{3, 4\}$ and $p \ge 5$ then $t(p) = 0$, $t = t_0 \le 4 \le k_0$. From (1) of Theorem 4.1, $\mathrm{Ker}_p(tW_3 k) = \{0\}$ and $\mathrm{Ker}_p(tW_4 k) = \{0\}$. Then from Observation 2.3, we obtain $H^{(3)}(G) = H^{(3)}(G')$, $P^{(4)}(G) = P^{(4)}(G')$ and $S^{(4)}(G) = S^{(4)}(G')$.

Case 2. $k_0 = 0$. As $t = t_0 \ne 0$ then, from (2) of Theorem 4.1, $\dim \mathrm{Ker}_p(tW_t k) = 1$ and $(1, 1, \dots, 1)$ is a basis of $\mathrm{Ker}_p(tW_t k)$. By Observation 2.3, there are $\lambda_h, \lambda_p, \lambda_s \in \{0, 1, -1\}$ such that $w_G^h - w_{G'}^h = \lambda_h(1, 1, \dots, 1)$, $w_G^p - w_{G'}^p = \lambda_p(1, 1, \dots, 1)$, $w_G^s - w_{G'}^s = \lambda_s(1, 1, \dots, 1)$.

If $\lambda_h = 1$, then $w_G^h = (1, 1, \dots, 1)$ and $w_{G'}^h = (0, 0, \dots, 0)$. Then in $G'$ there is no 3-homogeneous set, that is impossible according to Ramsey's theorem [11] which ensures that Ramsey's number $r(3, 3)$ is equal to 6. If $\lambda_h = -1$, $w_G^h = (0, 0, \dots, 0)$ and we conclude as above. Then $\lambda_h = 0$ and thus $H^{(3)}(G) = H^{(3)}(G')$.

If $\lambda_p = 1$, then $w_G^p = (1, 1, \dots, 1)$. So for all 4-element subsets $X$ of $V$, $G|_X \simeq P_4$, thus $G$ is 4-monomorphic. Then by Proposition 4.2, $G$ is 2-monomorphic, that implies $G$ is the empty graph or the complete graph, so $G$ does not contain a subgraph isomorphic to $P_4$, a contradiction. If $\lambda_p = -1$, then $w_{G'}^p = (1, 1, \dots, 1)$ and we conclude as above. Then $\lambda_p = 0$ and thus $P^{(4)}(G) = P^{(4)}(G')$.

If $\lambda_s = 1$, then $w_G^s = (1, 1, \dots, 1)$. So for all 4-element subsets $X$ of $V$, $G|_X \simeq K_{1,3}$ or $G|_X \simeq \overline{K_{1,3}}$, thus $G$ is 4-monomorphic up to complementation. Then by Proposition 4.3, $G$ is 3-monomorphic up to complementation. Let $v_0, v_1, v_2, v_3 \in V$ such that $G|_{\{v_0, v_1, v_2, v_3\}}$ or $\overline{G|_{\{v_0, v_1, v_2, v_3\}}}$ is the claw $(\{v_0, v_1, v_2, v_3\}, \{\{v_0, v_1\}, \{v_0, v_2\}, \{v_0, v_3\}\})$. We have $G|_{\{v_0, v_1, v_2\}} \not\simeq G|_{\{v_1, v_2, v_3\}}$ and $G|_{\{v_0, v_1, v_2\}} \not\simeq \overline{G|_{\{v_1, v_2, v_3\}}}$, this contradicts the fact that $G$ is 3-monomorphic up to complementation. If $\lambda_s = -1$, then $w_{G'}^s = (1, 1, \dots, 1)$, we conclude as above. Then $\lambda_s = 0$ and thus $S^{(4)}(G) = S^{(4)}(G')$. $\square$

**Acknowledgements** We are pleased to thank the anonymous referees for their helpful comments and suggestions.

**Open Access** This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article's Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article's Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/.

## References

1. Ben Amira, A.; Dammak, J.; Si Kaddour, H.: On a generalization of Kelly's combinatorial lemma. Turk. J. Math. **38**, 949–964 (2014)

2. Bondy, J.A.: Basic graph theory: paths and circuits. Handbook of Combinatorics, Vol. 1, 2, pp. 3–110. Elsevier Sci. B. V., Amsterdam (1995)

3. Bondy, J.A.; Hemminger, R.L.: Graph reconstruction—a survey. J. Graph Theory **1**(3), 227–268 (1977)

4. Dammak, J.; Lopez, G.; Pouzet, M.; Si Kaddour, H.: Hypomorphy of graphs up to complementation. J. Combin. Theory Ser. B **99**(1), 84–96 (2009)

<figure><img src="image_11.png" /></figure>
5. Dammak, J.; Lopez, G.; Pouzet, M.; Si Kaddour, H.: Boolean sum of graphs and reconstruction up to complementation. Adv. Pure Appl. Math. **4**(3), 315–349 (2013)

6. Fraïssé, R.: Theory of relations. North-Holland Publisher Co, Amsterdam (1st edn. 1986, 2nd ed. 2000).

7. Gottlieb, D.H.: A class of incidence matrices. Proc. Am. Math. Soc. **17**, 1233–1237 (1966)

8. Pouzet, M.: Application d'une propriété combinatoire des parties d'un ensemble aux groupes et aux relations. Math. Z. **150**, 117–134 (1976)

9. Pouzet, M.; Si Kaddour, H.: Isomorphy up to complementation. J. Comb. **7**(2–3), 285–305 (2016)

10. Pouzet, M.; Si Kaddour, H.; Trotignon, N.: Claw-freeness, 3-homogeneous subsets of a graph and a reconstruction problem. Contrib. Discrete Math. **6**(1), 86–97 (2011)

11. Ramsey, F.P.: On a problem of formal logic. Proc. Lond. Math. Soc. **30**(4), 264–286 (1929)

12. Ulam, S.M.: A Collection of Mathematical Problems. Intersciences Publishers, New York (1960)

13. Wilson, R.M.: A Diagonal Form for the Incidence Matrices of *t*-Subsets vs. *k*-Subsets. Eur. J. Comb. **11**(6), 609–615 (1990)

**Publisher's Note** Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

<figure><img src="image_12.png" /></figure>

<figure><img src="image_13.png" /></figure>