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

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?

• Yes, you're done. – user3482749 Jan 17 at 15:38
• 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? – Gregory J. Puleo Jan 17 at 22:40

## 2 Answers

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

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

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