# Discrete Mathematics, Graph Theory

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

-
This is not true for non-simple graphs. – JeremyKun Dec 1 '12 at 22:56
Does it have any relation to question 4 on this ongoing assignment here? – Douglas S. Stones Dec 1 '12 at 22:57
Indeed Douglas, two other questions on that assignment were asked earlier today, all by unregistered user(s). – amWhy Dec 1 '12 at 23:00
Another one has just been asked. – ՃՃՃ Dec 1 '12 at 23:06

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.