Sufficient conditions for a graph to be able to be represented by the join of two graphs I am looking for sufficient conditions for a simple graph to be able to be represented by the join of two other simple graphs both of which have order greater than or equal to $2$.
Some specific questions would be:


*

*What is number of edges in a graph needed to guarantee a graph can be represented by the join of two graph both with order greater than or equal to $2$.


*What does the minimum degree of each vertex need to be to guarantee a graph can be represented by the join of two graph both with order greater than or equal to $2$.

 A: Let $G$ have $n$ vertices, where $n\ge 4$. Say that a graph has property $J$ if it’s the join of two graphs each of order at least $2$. 
For the first question, if we start with $K_n$ and remove $n-2$ of the edges incident at a fixed vertex $v$, the resulting graph does not have property $J$. Thus, the minimum number of edges required to guarantee that $G$ has property $J$ is at least $$\binom{n}2-(n-2)+1=\binom{n}2-n+3\;.$$ And in fact this does the trick. 
Suppose that $G$ has at least $\binom{n}2-n+3$ edges. Then $\overline{G}$, the complement of $G$, has at most $n-3$ edges, and the largest component of $\overline{G}$ has at most $(n-3)+1=n-2$ vertices. Let $V_0$ be the set of vertices in the largest component of $\overline{G}$, and let $V_1$ be the remaining set of vertices. Then $|V_0|,|V_1|\ge 2$, and $\overline{G}$ has no edge between $V_0$ and $V_2$, so $G$ is the join of graphs on $V_0$ and $V_1$ and has property $J$.
So far I have only a partial answer to the second question, one showing that a fairly large bound is required . Suppose that $G$ is the join of $H$ and $K$. If $u$ and $v$ are vertices of $H$ and $K$, respectively, then we must have $\deg_Gu+\deg_Gv\ge n$. The weakest uniform minimum degree condition on $G$ that ensures this is requiring that $\deg_Gu\ge\left\lceil\frac{n}2\right\rceil$ for each vertex $u$ of $G$. However, this is insufficient to ensure that $G$ has the desired property. 
For a counterexample, let $n=2m$, and let $H$ and $K$ be copies of $K_m$ with vertices $u_0,\ldots,u_{m-1}$ and $v_0,\ldots,v_{m-1}$, respectively. Let $G$ be the disjoint union of $H$ and $K$ together with the edges $\{u_k,v_k\}$ for $k=0,\ldots,m-1$. Then $\deg_Gw=m=\frac{n}2$ for each vertex $w$ of $G$, but it’s easy to check that if $m\ge 3$, then $G$ does not have property $J$.
