Could a graph of order $n >2$ with two vertices of degree $n-1$ be a tree?

Question

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?

Answer 1

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

Answer 2

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