Finding minimum degree in a simple connected graph G if we have the maximum degree $\Delta$

209 Views Asked by At

I am seeking to find the minimum degree of a simple graph $G$ of order $n$ if the maximum degree $\Delta=n-1$.

1

There are 1 best solutions below

1
On

Clearly this has no single answer. All the question tells us is that there is a vertex that shares an edge with every other vertex; but it tells us nothing more; we can say that minimum degree is at least $1$ but we already knew that because it was connected. Take any connected graph on $3$ vertices and you will see what I mean. Now if you mean a graph with no cycles, then the answer is $1$ because adding any edge barring the ones joining each vertex to the vertex of maximum degree will give you a cycle.