7
$\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$

1 Answer 1

6
$\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$
9
  • $\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, 2015 at 21:31
  • $\begingroup$ The proof is now added to the answer. $\endgroup$ Apr 28, 2015 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, 2015 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$ Apr 28, 2015 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$ Apr 28, 2015 at 21:06

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .