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.
[Math] Let *G* be a simple graph having no isolated vertex and no induced subgraph with exactly 2 edges.
graph theory
Related Solutions
If you allow loops and/or multiple edges between vertices, then such a graph exists. Take $1$ vertex with $17$ loops, or two vertices with $17$ edges between them, and let the other vertices be isolated.
Now assuming we are working with a simple graph (no loops, and no multiple edges), then no such graph exists. This is because the maximum number of edges that can exist on a simple graph of $6$ vertices is $15$. Can you see why?
$P_4$ must mean a $4$-vertex path (a path of length $3$), otherwise the claim is not true; the $5$-vertex cycle is a counter-example.
Let $C$ an odd cycle of smallest length (if any) in $G$. If $c \geq 5$ then any chord (edge in $G \setminus C$ connecting two vertices in $C$) implies...
the existence of a smaller odd-length cycle in $G$ (the chord "splits" $C$ into an odd-length cycle and an even-length cycle). E.g.:
Hence $C$ (if it exists) is an induced subgraph, and thus $C$ (and hence $G$) contains an induced $P_4$ subgraph, giving a contradiction. Hence $C$ does not exist.
Hence $G$ contains no odd length cycles, and is thus is a connected subgraph of $K_{n,m}$ for some $n,m$. Let the parts be denoted $N$ and $M$.
If $u \in N$ and $v \in M$, then the shortest path between $u$ and $v$ is...
an induced path of odd length. Since $G$ contains no induced paths of length $\geq 3$, we must have that $u$ and $v$ are adjacent.
Hence $G=K_{n,m}$.
Related Question
- [Math] Let $G$ be a simple graph on $10$ vertices and $38$ edges. Prove that $G$ contains $K_4$ as an induced subgraph.
- [Math] Finding the largest triangle-free induced subgraph in a given simple graph $G$ is NP-Complete.
- If every $k$-vertex induced subgraph of $G$ has $m$ edges, then $G$ is either complete or empty.
Best Answer
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.