# A graph consisting of cliques pairwise intersecting in 1 point

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$?

• Just to summarize the two good examples below, There are $q=n\binom{n-1}{2}$ edges you require. There is an example with $N=\binom{n}{2}$ vertices (in some sense the only one as far as the groups $S_i$ are concerned). If you throw in some or all of the unrequired edges your conditions are still met. – Aaron Meyerowitz Nov 8 '16 at 3:32

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.

• These graphs are the linegraphs of the complete graphs. The cliques are the sets of edges incident with one vertex. – Brendan McKay Nov 8 '16 at 0:02

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!$).

• Ah yes, this is a more direct proof. It's nice that you can simply make the map $F$ arbitrary. I suppose that the fact that we are dealing with line graphs of complete graphs (and cliques of order $n-1$ in $G$ correspond to vertices of $K_n$) makes this strategy a sensible one :-). – Jon Noel Nov 8 '16 at 10:17

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.

• Right. As well as the linegraphs of complete graphs, one can add extra edges without violating any of the OP's three properties. Some additional condition is required to ensure uniqueness. – Brendan McKay Nov 8 '16 at 3:14
• @BrendanMcKay, "additional condition is required to ensure uniqueness" I am in the middle of typing an additional answer about the uniqueness (in a sense in the sense of JonNoel :) ). – Włodzimierz Holsztyński Nov 8 '16 at 4:28