2
$\begingroup$

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.

$\endgroup$
0

2 Answers 2

2
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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:

enter image description here

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:

enter image description here

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

enter image description here

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.

$\endgroup$

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.