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)$.
Discrete Mathematics, Graph Theory
0
$\begingroup$
graph-theory
discrete-mathematics
-
0[Another one](http://math.stackexchange.com/questions/248872/discrete-mathematics-more-graph-theory) has just been asked. – 2012-12-01
1 Answers
3
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.