Under some conditions, Prove that $χ(G) ≤(\omega(G)+1)\omega(G)/2$. Let $G=(V,E)$ be a graph s.t for each pair of (different) edges $e_1,e_2$  with no common vertex, there is an edge $e_3$, which has common vertex with $e_1$ and common vertex with $e_2$. Prove that $χ(G)\le (ω(G)+1)ω(G)/2$.
Here is my (unsuccessful) try:
(induction on $card(V)$) (for $card(V)$$=$$1,2,3$ it's easy):
Consider a colouring of $G$ with $χ(G)$ colors. Now $V$ is partitioned to $V(1),..,V(χ(G))$ nonempty independent sets. let $W$ be a clique of size $ω(G)$ WLOG his vertices are in $V(1),..,V(ω(G))$. now look at $G'$$=$$G$$-${$V(1),..,V(ω(G))$}. if $χ(G')$$=$$χ(G)-ω(G)$ and $ω(G')$$<$$ω(G)$ than (as $G'$ obviously satisfies the conditions) we could finish this with the induction asumption (as we would get $χ(G)-ω(G)$$=$$χ(G')$$≤$$(ω(G')+1)(ω(G'))/2$$≤$$(ω(G))(ω(G)-1)/2$ thus $χ(G)$ $≤$ $(ω(G)+1)(ω(G))/2$).
But here I of course assumed that there is a such a colouring and a clique. must there exist such a coluring and a clique? any other ideas? thanks in advance.
 A: If you meditate carefully on the the $\omega(G)(\omega(G)+1)/2 = {\omega(G)+1\choose 2}$ term, you may recall that this equals $1+2+\cdots+\omega(G)$.  That indicates that the proof may be something like: delete an entire clique $A\subseteq V(G)$ out of $G$ such that the clique number goes down by $1$ (or more).  Then by induction, we have a ${\omega(G)\choose 2}$-coloring of $G-A$, and if we add back the elements of $A$ each with a new color, then we now have a ${\omega(G)+1\choose 2}$-coloring of the entire graph $G$.  
Indeed, this approach works.  The claim easily holds if $\omega(G) = 1$, so we ignore that case.  We prove the intermediate claim that any two maximum size cliques in $G$ have a vertex in common, but to prove that, we first show that the bipartite graph induced between two maximum size cliques has some special properties.  First suppose $S,T$ are cliques of maximum size $G$ and suppose further that $S\cap T=\emptyset$ (this proof does not need to be phrased as a contradiction, but contradiction feels more natural here).  Then let $B$ be the bipartite graph $G[S,T]$, which has the edges in $G$ which are of the form $st$ for $s\in S$ and $t\in T$.  We show that if $u,v\in S$, then either $N_B(u)\subseteq N_B(v)$, or the reverse inclusion holds.  Indeed, suppose neither $\subseteq$ nor $\supseteq$ holds.  Then there exist $w,x\in T$ such that the only edges in $G[\{u,v,w,x\}]$ are $uv$ and $wx$, a contradiction to our assuimption. It follows that we can order $S = \{s_1,\dots,s_k\}$ where $N_B(s_i)\subseteq N_B(s_j)$ if $1\leq i<j\leq k$.  
Since $|S| = |T| = \omega(G)$, $N_B(s_k)$ is a proper subset of $T$ and we may fix some $t\in T\setminus N_B(s_k)$.  Suppose $N_B(s_1)\neq N_B(s_k)$.  Then $|T\setminus N_B(s_1)|\geq 2$ and we may find some $t'\in T\setminus N_B(s_1)$ for which $t'\neq t$.  This is a contradiction since then $G[\{s_1,s_k,t,t'\}]$ has only the edges $s_1s_k$ and $tt'$.  So $|T\setminus N_B(s_1)|\leq 1$ and it follows that $N_B(s_1) = N_B(s_k)$, hence $N_B(s) = N_B(s')$ for all $s,s'\in S$  This is a contradiction since then $G$ has a larger clique than is possible.  So $S\cap T$ are not in fact disjoint and the desired argument works.  
If you get stuck in understanding this proof, especially the bipartite graph part, just draw the picture until it cliques.  
A: Gave it another shot (after two years) and solved it. 
Let $W$ be a clique in $G$ of size $\omega(G)$. For each $e\in E(W)$ define $D_{e}=\{u\in V(G)\setminus V(W)\mid N_{W}(u)\cap e=\emptyset\}$. For each $v\in V(W)$ define $D_{v}=\{v\}\cup \{u\in V(G)\setminus V(W)\mid N_{W}(u)=V(W)\setminus \{v\}\}$. 
Let $X=V(W)\cup E(W)$. Claim 1: For every $x\in X$,  $D_{x}$ is an independent set.  Proof: Assume otherwise. Take $x\in X$ s.t. $D_{x}$ is not an independent set. Take  $v_1 , v_2 \in D_x$ s.t. $\{v_1, v_2\}\in E(G)$.  If $x\in V(W)$ then clearly $x\notin \{v_1, v_2\}$ (because if say, $x=v_1$, then we get that $x\in N_W (v_2)$ which contradicts the fact that $v_2\in D_x$)  and thus $\{v_1, v_2\}\cup (V(W)\setminus \{x\})$ forms a clique of size $\omega(G)+1$, a contradiction. Thus $x=e\in E(W)$. $e$ and $\{v_1, v_2\}$ are a pair of edges that share no common vertex. Thus there is some $v\in e$ and $i\in \{1,2\}$ s.t. $\{v, v_i \}\in E(G)$, so $v_i\notin D_e$, a contradiction.  Claim 2: $V(G)=\cup_{x\in X} D_x$.  Proof: Let $v\in V(G)$. If $v\in V(W)$, then $v\in D_v \subseteq \cup_{x\in X} D_x$. Now suppose that $v\in V(G)\setminus V(W)$. Clearly, $N_W (v)\subsetneq W$ (otherwise $\{v\}\cup V(W)$ forms a clique of size $\omega(G)+1$). Now if $\mid N_W (v)\mid <\omega(G)-1 $, then there exists $e\in E(W)$ s.t. $e\cap N_W (v) = \emptyset $,
so $v\in D_e \subseteq \cup_{x\in X} D_x$. Thus we can assume that $\mid N_W (v)\mid=\omega(G)-1$. Now writing $\{s\}=V(W)\setminus N_W (V)$, we get $v\in D_s\subseteq \cup_{x\in X} D_x$. Claim 3: $χ(G)≤{\omega(G)+1\choose 2}$.  Proof: $\mid X\mid =\mid V(W)\mid + \mid E(W)\mid = \omega(G)+{\omega(G) \choose 2}= {\omega(G)+1\choose 2}$. Write $X=\{x_1,...,x_{\omega(G)+1\choose 2}\}$. For each $i\in \{1,...,{\omega(G)+1\choose 2}\}$ define $T_i=D_{x_i}\setminus (D_{x_1}\cup...\cup D_{x_{i-1}})$. Now $f:V(G)\rightarrow \{1,...,{\omega(G)+1\choose 2}\}$, (well-)defined via $f_{\big|T_i}\equiv i$, is a (legitimate) coloring of $G$ with at most ${\omega(G)+1\choose 2}$ colors. 
