4
$\begingroup$

Show that if a self-complementary graph contains a pendant vertex, then it must have at least another pendant vertex.

Let $G$ be a graph of order $n$, so it has $n(n-1)/4$ edges, just like its complement. Asume that there is only one pendant vertex $v$, so $d(v)=1$, it means that $G^c$ has a vertex $w$ with $d(w)=n-2$. Then $G$ must also have a vertex of degree $n-2$ and $G^c$ one of degree $1$.

I guess I can reach somehow a contradiction with the fact that $n=4k$ or $n=4k+1$, but I got stuck there.

Can you give me a hint please? Like "this fact may be useful..."

$\endgroup$
4
$\begingroup$

A very nice problem. I did not know it, but I find it hard to give a hint without giving away the full proof. Here is a try: consider the adjacency of the vertex of degree 1 and the vertex of degree $n-2$.

Here is the proof then.

Suppose there is only one vertex $v$ of degree 1. Then there is also only one vertex $w$ of degree $n-2$. Let $\phi$ be an isomorphism mapping $G$ to its complement. Clearly $\phi(v)=w$ and $\phi(w)=v$. But this implies that $v$ and $w$ are adjacent in $G$, if and only if they are adjacent in the complement.

This contradiction shows that there must be another vertex of degree 1.

$\endgroup$
8
  • $\begingroup$ Mmm, I don't know...$G$ must have $n-2$ vertices with degree greater or equal than 1...I still can't get it :'( $\endgroup$ – Lotte Apr 27 '15 at 21:31
  • $\begingroup$ The proof is now added to the answer. $\endgroup$ – Leen Droogendijk Apr 28 '15 at 6:06
  • $\begingroup$ I have alredy thought something similar but I couldn't keep going because $v$ is a vertex of $G$ and $w$ is a vertex of $G^c$, if they are correspondent by $\phi$ then they must have the same degree, isn't that correct? I know this: we have $v$ of degree 1 in $G$, via $\phi$ we get $\phi(v)=v'$ of degree 1 in $G^c$, in a similar way for $\phi(w)=w'$. And those are unique... Sorry, I'm very confused :/ $\endgroup$ – Lotte Apr 28 '15 at 18:19
  • 1
    $\begingroup$ $G$ and $G^c$ have the same vertices, they only have different edges. $v$ has degree 1 in $G$, but it has degree $n-2$ in $G^c$. For $w$ it is the other way around. Therefore $\phi(v)$ must be $w$ and v.v. $\endgroup$ – Leen Droogendijk Apr 28 '15 at 19:04
  • 1
    $\begingroup$ @Hermine If that doesn't cut it, I suggest simply trying to draw the graphs, focusing on $v$ and $w$. First suppose that $v$ and $w$ are neighbors, and find the contradiction. Then suppose they aren't neighbors - you'll reach another contradiction. $\endgroup$ – Manuel Lafond Apr 28 '15 at 21:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.