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.

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

share|improve this question
    
This is not true for non-simple graphs. –  JeremyKun Dec 1 '12 at 22:56
4  
Does it have any relation to question 4 on this ongoing assignment here? –  Douglas S. Stones Dec 1 '12 at 22:57
2  
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
    
Welcome to math.SE: since you are new, I wanted to let you know a few things about the site. In order to get the best possible answers, it is helpful if you say in what context you encountered the problem, and what your thoughts on it are; this will prevent people from telling you things you already know, and help them give their answers at the right level. If this is homework, please add the homework tag; people will still help, so don't worry. Also, many find the use of imperative ("Prove", "Solve", etc.) to be rude when asking for help; please consider rewriting your post. –  Julian Kuelshammer Dec 1 '12 at 23:18

1 Answer 1

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.

share|improve this answer

Your Answer

 
discard

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