Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question

1 Answer 1

up vote 3 down vote accepted

$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}$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.