2
$\begingroup$

I am trying to characterize the connected graphs $G$ which
a) contain $K_{1,2}$ as a subgraph
b) contain $K_{1,2}$ as an induced subgraph

For part a), I think that it is necessary and sufficient for $G$ to have at least $3 $ vertices, for $K_{1,2}$ is not a subgraph of $G$ if and only if $G$ has no vertex of degree at least $2$, if and only if $G$'s vertices all have degree at most $1$, if and only if $G$ has less than $3$ vertices, for if it had $3$ or more vertices but all had degree at most $1$, it would not be connected.

I am not sure how to approach part b) though. The condition that $G$ has a vertex of degree at least $2$ (which I started with in part a) ) is not sufficient for $G$ to contain $K_{1,2}$ as an induced subgraph, since the "triangle graph" (is there a proper name for this?) has vertices of degree $2$ but no induced subgraph which is $K_{1,2}$.

Any help is appreciated!

$\endgroup$

1 Answer 1

3
$\begingroup$

$G\not\cong K_{|G|}$ should be what you are looking for. If a connected graph is not the complete graph, then it has two vertices $a,b$ at distance $>1$, hence also two $a,c$ vertices (with $c$ on a shortest path from $a$ to $b$) at distance $=2$. Then if $d$ is a common neighbour of $a$ and $c$, we are done: The graph induced by $\{a,c,d\}$ is $\cong K_{1,2}$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .