1
$\begingroup$

I need to answer to this (apparently) simple question. In my opinion, since a tree has $n-1$ edges, a graph with these characteristics couldn't exist. In fact, whatever $n$ is chosen, I don't know what happens to the other vertices of the graph but I know that two of them have degree $n-1$. This means already having 2(n-1) edges in the graph that is larger than n-1 and therefore can not be a tree (in other words I am forced to define a cycle that in trees are not allowed).

Can it be reasonable to answer the question in this way?

$\endgroup$
  • $\begingroup$ Yes, you're done. $\endgroup$ – user3482749 Jan 17 at 15:38
  • $\begingroup$ Note that there's a small flaw in your argument: as written, it would seem to apply just as well to $n=2$, yet $K_2$ is a tree both of whose vertices have degree $n-1$. Do you see how you might be overcounting the number of edges in the graph? $\endgroup$ – Gregory J. Puleo Jan 17 at 22:40
2
$\begingroup$

Yes you are right, If $G$ (of order $n>2$) has two vertices of degree $n-1$, then it cannot be a tree :

Let $u,v \in V(G)$ such that $d(u)=d(v)=n-1$. Then $u$ and $v$ are connected to all vertices of $G$. With $n>2$, let $w$ be a vertices of $G\backslash\{u,v\}$. Then (with $\sim$ denoting connection):

  • $u\sim v$
  • $v\sim w$
  • $u\sim w$

Therefore $(uvw)$ is a cycle, $G$ is not a tree.

Edit As mentionned by Ranveer Singh, if $G$ has one vertex of degree $n-1$, then $G$ is a tree if and only if all other vertices have degree 1. Indeed : $$ \sum_{i\in V(G)} d(i) = 2m$$ Any tree on $n$ vertices have $n-1$ edges, therefore, with $v$ the vertice of degree $n-1$ : $$ \sum_{i\in V(G)} d(i) = 2(n-1)$$ $$ \sum_{i\in V(G)\backslash \{v\}} d(i) = n-1$$

For $G$ to be a tree, $G$ needs to be connected, therefore $d(i)>0$ and $$ \sum_{i\in V(G)} d(i) = 2(n-1) \Leftrightarrow \ \forall i \in V(G)\backslash \{v\}, \ d(i)=1$$

$\endgroup$
2
$\begingroup$

I will slightly generalize this. If $n>2$, and a vertex has degree $n-1$, then $G$ can be tree only if rest of $n-1$ vertices have degree equals to 1. This is because the summation of the degrees $n-1+(n-1)\times 1$ is twice the number of edges, that is, $2(n-1)$. Moreover, in this case, the tree is unique (star graph).

$\endgroup$
  • $\begingroup$ Good addition, i will amend my answer to reflect this. $\endgroup$ – Thomas Lesgourgues Jan 17 at 16:26

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.