Let $G$ be a connected graph in which every pair of edges has an endpoint in common. Show that $G$ is either a star or the complete graph $K(3)$.
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
Assume $G$ is not a star. Then there exist two vertices $a,b$ with degree $\ne 1$. Since $G$ is connected, both degrees are $\ge 2$. Let $ax$ and $ay$ be two different edges at $a$. Then at least one of $x,y$ is $\ne b$, say $x\ne b$. Let $bz$ be any edge at $b$. Then it has a vertex in common with $ax$, hence $z=a$ or $z=x$. We conclude that $b$ has degree $2$ and exactly two edges $ba$ and $bx$. Similarly, $a$ is of degree exactly two and has edges $ab$ and $ax$. By the same argument, $x$ cannot have degree $>2$ and there cannot be any additional vertices.