In graph theory, the degree of a vertex is the number of edges connecting it. A vertex v where deg(v) = 1 is often called an "leaf vertex" because it is connected to one other and doesn't have a path anywhere else. Like the leaf on a tree. A vertex v where deg(v) = m ≥ 2 is sometimes called a "branch vertex", again like a branch on a tree, which can be straight or sometimes fork.
We require at least one vertex of degree at least m, and we are trying to minimize n. So, let's choose exactly one branch vertex with degree m, and all others being leaves. It would look like a spikey loofah if we drew it. Thus, the minimum n we could have would be
min n = m + 1
where the 1 is the branch vertex of degree m, and m are the leaf vertices of degree 1 hanging off it. [As an aside, this is sometimes called a "dominating vertex".]
Since we are paranoid, we want to make sure we have a valid graph by cross checking with the degree sum formula
∑ deg(v) = 2 E
But this checks out, because we have
m + 1 (m times) = 2 m
So our graph is valid and we haven't accidentally missed an edge or vertex.
Feel free to contact me for tutoring if you'd like more help with discrete math. Cheers.
