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

  • $\begingroup$ 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. $\endgroup$ – 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.

  • 3
    $\begingroup$ These graphs are the linegraphs of the complete graphs. The cliques are the sets of edges incident with one vertex. $\endgroup$ – 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!$).

  • 1
    $\begingroup$ 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 :-). $\endgroup$ – 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.

  • $\begingroup$ 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. $\endgroup$ – Brendan McKay Nov 8 '16 at 3:14
  • $\begingroup$ @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 :) ). $\endgroup$ – Włodzimierz Holsztyński Nov 8 '16 at 4:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.