Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|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

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|cite|improve this answer

Your Answer

 
discard

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