This question is inspired by a Andrew D. King's comment in [Linear intersection number and coloring (not chromatic) number](https://mathoverflow.net/questions/199128/linear-intersection-number-and-coloring-not-chromatic-number)




---


A *linear hypergraph* is a pair $\pi=(X, L)$ where $X\neq \emptyset$ is a set and $L\subseteq {\cal P}(X)$ has the following properties:


1. for $e\in L$ we have $|e|\geq 2$;
2. if $e\_1\neq e\_2 \in L$ then $|e\_1\cap e\_2|\leq 1$.


We set $X(\pi)=X$ and $L(\pi)=L$. The *graph* $G\_\pi$ *associated to* a linear hypergraph $\pi$ is given by $G=(V,E)$ where $V = L$ and $E = \{\{e\_1, e\_2\} \subseteq L: e\_1\neq e\_2\text{ and } e\_1\cap e\_2\neq \emptyset\}$. It turns out that for any graph $G$ there is a linear hypergraph $\pi$ such that $G\cong G\_\pi$. For any graph $G$ the we set $$\ell(G) := \text{min}\{|X(\pi)|:\pi \text{ is a linear hypergraph such that } G\_{\pi} \cong G\}$$ and call this the *linear intersection number* of $G$. (For infinite graphs, this concept is boring: $\ell(G) = |V(G)|$ for infinite graphs.)


For any finite graph $G$ let $\Delta(G)$ be the maximum degree.


Is there a finite graph $G$ such that $\Delta(G) > \ell(G)$?



Linear intersection number and maximum degree
Yes there is such a graph. Consider the following hypergraph $\pi = (X, L)$ where


* $X =\{1,2,\ldots 6\}$;
* $L = \big\{\{1,2,3\}\big\} \cup \big\{\{a,z\}: a\in \{1,2,3\}, z\in\{4,5,6\}\big\}$.


Let $v\_0 = \{1,2,3\}$ and we set $G:=G\_\pi$. Then clearly $\ell(G) \leq 6$, but $\Delta(G) \geq \text{deg}(v\_0) = 9$. So $\Delta(G) > \ell(G)$.


