A graph consisting of cliques pairwise intersecting in 1 point

Question

Suppose we have a positive integer $n\geq 4$. We call a graph $G=(V,E)$ an $K^{(n)}_{n-1}$-graph if

1. there are $n$ subsets $S_1,\ldots, S_n$, each consisting of $n-1$ points, and each are cliques;
2. for positive integers $i<j\leq n$ we have $|S_i\cap S_j| = 1$, and
3. for all $v\in V$ there are positive integers $i<j\leq n$ such that $S_i \cap S_j = \{v\}$.

If $G_1, G_2$ are both $K^{(n)}_{n-1}$-graphs, do we have $G_1\cong G_2$?

Answer 1

The answer is yes (in a certain sense; see below). This proof seems a bit long... so perhaps someone can come up with an easier argument!

The assumption that the sets form cliques in a graph seems to be irrelevant here. In fact, this problem isn't really a "graph problem" at all, so let's rephrase it in terms of hypergraphs. We want to show that there is unique (up to isomorphism) $(n-1)$-uniform hypergraph $\mathcal{H}$ such that

1. $\mathcal{H}$ has exactly $n$ edges,

2. any two edges of $\mathcal{H}$ intersect on exactly one vertex, and

3. for every vertex $v$, there exists a pair $e,e'$ of hyperedges with $e\cap e'=\{v\}$.

Claim 1: $\mathcal{H}$ has at most $\binom{n}{2}$ vertices.

Proof: Consider the function which maps each vertex $v$ to a pair of hyperedges whose intersection is $\{v\}$. This map is injective. $\square$

Okay, now order the edges of $\mathcal{H}$ by $e_1,\dots,e_n$ in an arbitrary order and let $\mathcal{H}_k$ be the subhypergraph of $\mathcal{H}$ induced by the hyperedges $e_1,\dots,e_k$. Clearly, $\mathcal{H}_1$ consists of $n-1$ vertices contained in a single hyperedge.

Claim 2: For $k\geq2$ we have $|V(\mathcal{H}_k)|\geq |V(\mathcal{H}_{k-1})| + n-k$.

Proof: By assumption, $e_k$ intersects each of the edges $e_1,\dots,e_{k-1}$ on exactly one vertex. Therefore, there must be at least $(n-1)-(k-1) = n-k$ vertices of $e_k$ not contained in any of the edges $e_1,\dots,e_{k-1}$. This completes the proof. $\square$

So, by Claim 2,

$$|V(\mathcal{H})| \geq |V(\mathcal{H}_1)| + (|V(\mathcal{H}_2)|-|V(\mathcal{H}_1)|) + \dots +(|V(\mathcal{H}_n)|-|V(\mathcal{H}_{n-1})|)$$ $$= (n-1) + (n-2)+\dots+1+0 = \binom{n}{2}.$$ Combining this with Claim 1, we see that we must have $|V(\mathcal{H})|=\binom{n}{2}$. Moreover, it must be the case that $$|V(\mathcal{H}_k)| = \binom{n}{2} - \binom{n-k}{2}$$ for $0\leq k\leq n$ (otherwise, we could apply Claim 2 to obtain $|V(\mathcal{H})|>\binom{n}{2}$, contradicting Claim 1).

In particular, we get that any vertex $v$ is contained in exactly two hyperedges of $\mathcal{H}$ (otherwise, if we let $e_1,e_2,e_3$ be the three hyperedges containing $v$, then this contradicts the fact that $|V(\mathcal{H}_3)|=3n-6$).

Now, let us show that $\mathcal{H}_k$ is uniquely determined (up to isomorphism) for each $k$ by induction. The result is trivial for $k=1$. Now for $k\geq2$, we can assume (by induction) that $\mathcal{H}_{k-1}$ contains no vertex of degree greater than two and that each hyperedge contains exactly $n-k+1$ vertices of degree one. By the above arguments, the graph $\mathcal{H}_k$ must be constructed from $\mathcal{H}_{k-1}$ by

(a) adding a set $A$ of $n-k$ new vertices, and

(b) adding a new hyperedge $e_k$ containing $A$ and containing exactly one vertex $v_i$ of degree one from the hyperedge $e_i$ for $1\leq i\leq k-1$.

All that remains is to show that any such choice yields the same hypergraph, up to isomorphism. For $1\leq i\leq k-1$, let $u_i$ and $v_i$ be (possibly different) vertices of $e_i$ of degree one. There is an isomorphism from the hypergraph obtained by adding the edge $A\cup \{u_1,\dots,u_{k-1}\}$ and the hypergraph obtained by adding the edge $A\cup \{v_1,\dots,v_{k-1}\}$ where $v_i\mapsto u_i$, $u_i\mapsto v_i$ and every other vertex simply maps to itself. This completes the proof.

Edit: As others have pointed out, what I have proved is that these graphs are unique under the additional assumption that every edge of $G$ is contained in one of the cliques $S_1,...,S_n$. Without this assumption, the class of graphs is closed under adding edges, and therefore we cannot have uniqueness. I originally interpreted the problem as having this assumption, but I do agree that it was not included in the statement.

Answer 2

Let me show the uniqueness in the sense of @JonNoel of Dominic's construction minus edges. My solution is following the earlier @JonNoel's Answer.

DEFINITION 1   An $n$-system is an ordered pair $\ \mathbf L := (V\ \mathbb L)\ $ where $\ V\ $ is a set such that $\ |V|\ge 3,\ $ and $\ \mathbb L\ $ is a family of sets such that $\ |\mathbb L|=n,\ $ and $\ \forall_{S\in\mathbb L}\ |S|=n-1,\ $ and

$$ \forall_{\{S\ T\}\in\binom {\mathbb L}2}\quad |S\cap T|=1 $$ and finally: $$ \forall_{v\in V}\ \exists_{\{S\ T\}\in\binom {\mathbb L}2} \quad v\in S\cap T $$

TERMINOLOGY:   call elements $\ S\in\mathbb L\ $ to be lines.

Lemma--Uniqueness ($\exists!\ $ means there exists exactly one) $$\forall_{v\in V}\ \exists!_{\{S\ T\}\in\binom{\mathbb L}2} \ S\cap T=\{v\}$$

PROOF   Let $\ S\in\mathbb L\ $ be fixed. For each $\ v\in S\ $ select one $\ T_v\in\mathbb L\ $ such that $\ S\cap T_v=\{v\}.\ $ Then $\ T_v\ $ cannot have any $\ w\in S\ $ different from $\ v.\ $ This means that every two lines among $\ T_v\ (v\in S)\ $ are different hence there are $\ n-1\ $ of them. This means that together with $\ S\ $ there are no other lines. Thus there is no line T which contains $\ v\in S\ $ but is different from $\ T_v.\ $ END of PROOF

 

DEFINITION 2   Two $n$-systems $\ \mathbf V:=(V\ \mathbb L)\ $ and $\ \mathbf M:=(W\ \mathbb M)\ $ are called isomorphic $\ \Leftarrow:\Rightarrow\ \exists_{f:V\rightarrow W}\ $ such that $\ f\ $ is a bijection, and $\ \forall_{S\in\mathbb L}\ f(S)\in\mathbb M,\ $

 

THEOREM   Every two $n$-systems $\ \mathbf V:=(V\ \mathbb L)\ $ and $\ \mathbf M:=(W\ \mathbb M)\ $ are isomorphic.

PROOF   Let $\ F : \mathbb L\rightarrow\mathbb M\ $ be an arbitrary bijection (between $n$-element sets). Define $\ f:V\rightarrow W\ $ as follows (cf. the Lemma above):

$$ f(v) = w\ \Leftarrow:\Rightarrow\ w\in F(S)\cap F(T) $$

where $\ \{S\ T\}\ $ is the only pair of lines such that $\ v\in S\cap T.\ $ END of PROF

REMARK   The automorphism group of an $n$-system is the group induced by the symmetric group of its lines (it has order $n!$).

Answer 3

Formally speaking, the answer is NO, as I will show. Otherwise, @JonNoel had a good insight.

NOTATION   $\ \binom An\ :=\ \left\{ X\subseteq A: |X|=n\right\}\ $ for arbitrary set $A$.

First, let me show the existence (Dominic has not asked about the existence but it seems to be enlightening. This will be a part of my formal answer anyway.

Let $P$ be a set of cardinality $\ n = |P|\ge 3,\ $ however, the non-uniqueness will hold for every $\ n\ge 4.\ $ Define:

$$ V\ :=\ \binom P{n-2} $$ $$ E\ :=\ \left\{\left\{K\ M\right\}\in \binom V2 :\ |K\cup M| = n-1\right\} $$

Thus, for $\ n\ge 4\ $ the graph $(V\ E)\ $ is not complete. Next, define:

$$ \mathbb L\ :=\ \left\{\binom S{n-2}:\ S\in\binom P{n-1}\right\} $$

Thus, $\ |\mathbb L| = n\ $ and $\ \forall_{\mathbf S\in\mathbb L}\ |S|=n-1,\ $ just as required by the Question. Also, every $\ \mathbf S\in\mathbb L\ $ is a clique, and $$\forall_{\mathbf S\ \mathbf T\in \mathbb L}\ (\mathbf S\ne \mathbf T\ \Rightarrow\ |\mathbf S\cap \mathbf T| = 1) $$ and $$\forall_{\pi\in P} \ \exists_{\{\mathbf S\ \mathbf T\}\in\binom {\mathbb L}2}\quad p\in \mathbf S\cap \mathbf T $$

We have obtained an example for every $\ n\ge 3.\ $ However, for $n\ \ge 4\ $ we may replace the set of edges $\ E\ $ by the complete set $\ F:=\binom P2,\ $ and let all other data be the same. That provides a graph nonisomorphic to the given one, for each $\ n\ge 4,\ $ which shows that the answer to the Question is NO.

REMARK 1   $\ \mathbb L\ $ is exactly the set of all cliques of $\ (V\ E)\ $ for every $\ n\ge 4$.

REMARK 2   As @JoelNoe seemed to suggest, an introduction of edges into the Question was not essential, and it has caused the negative response.