# Let *G* be a simple graph having no isolated vertex and no induced subgraph with exactly 2 edges.

Let G be a simple graph having no isolated vertex and no induced subgraph with exactly 2 edges. Prove that G is a complete graph.

I think I have to prove it using a contradiction but I am not sure.

First, we claim that $G$ is connected. Suppose, on the contary, that two vertices $u$ and $v$ are in different components. Since $u$ and $v$ are not isolated, there is a vertex $u'$ adjacent to $u$ and a vertex $v'$ adjacent to $v$. Now consider the induced subgraph on $\{u,u',v,v'\}$; it contains the edges $uu'$ and $vv'$, but by assumption it must not contain only two edges, so it must contain another edge, either $uv$, $uv'$, $u'v$, or $u'v'$, which in any case violates our assumption that $u$ and $v$ are in different components. Therefore $G$ is connected.

Suppose that $G$ is not a complete graph. Let $A$ be a maximal complete subgraph of $G$, and let $u$ be an vertex of $G$ not in $A$. Without loss of generality, we can assume that $u$ is adjacent to a vertex $a \in A$. (Proof: Choose an arbitrary vertex $a\in A$; since $G$ is connected, there is a path from $a$ to $u$, and along this path let $a'$ be the last vertex in $A$, and let the next vertex along the path be $u'$. Then $u' \notin A$, so by replacing $a$ and $u$ by $a'$ and $u'$ respectively, we may assume that $u$ is adjacent to $a$.) Now let $b$ be any vertex in $A$ distinct from $a$, and consider the induced subgraph on $\{a,b,u\}$. We are assuming that the edge $au$ is in $G$, and since $a,b\in A$ and $A$ is a complete graph we also have $ab$ in $G$; but since the induced subgraph cannot contain exactly two edges, we must also have $bu$ in $G$. Thus $u$ is a adjacent to every vertex in $A$, so $A\cup\{u\}$ is a complete subgraph, contradicting the maximality of $A$. This completes the proof.

Let $v$ be a vertex of such a graph $G$, and let $N(v)$ be the neighborhood of $v$.

If there's a non-edge induced by $N(v)$, then we get a $2$-edge induced subgraph indicated below:

So $v \cup N(v)$ induces a complete graph. We will argue there are no more vertices, and conseqently $G$ is the complete graph on $v \cup N(v)$.

A vertex $w$ outside of $\{v\} \cup N(v)$ might be be adjacent to a vertex in $N(v)$, but this would give rise to a $2$-edge induced subgraph indicated below:

Instead, $w$ (since it's not isolated) must be adjacent to some vertex $x \not\in \{v\} \cup N(v)$:

There are no edges between $v \cup N(v)$ and $x$ (for the same reason there aren't any for $w$), so we get a $2$-edge induced subgraph (the orange edge above, along with any edge with endpoint $v$), giving a contradiction.