3
$\begingroup$

I'm learning an algorithm for graphs of maximum degree three.

My question is: should the graph of that type have at least one vertex with degree three.

For example if the maximum degree of some graph is 2, can we say that this graph is maximum degree three.

Thank you

$\endgroup$
2
  • 2
    $\begingroup$ It ultimately depends on the definition you use, but usually a "maximum" does not require a sharp bound. $\endgroup$
    – dkaeae
    May 23, 2019 at 12:05
  • 1
    $\begingroup$ Usually, "maximum degree 3" is really "maximum degree at most 3", i.e., "all vertices have degree at most 3". You could say "maximum degree exactly 3" if you want the maximum degree to be exactly 3. But the exact meaning really depends on the context. $\endgroup$ May 23, 2019 at 13:20

2 Answers 2

4
$\begingroup$

In general it is impossible to tell. When people say that a graph has maximum degree 3, they could mean two different things:

  • The maximal degree of a vertex in the graph is 3.
  • All vertices in the graph have degree at most 3.

Similarly, a function of degree $d$ sometimes means a function of degree exactly $d$, and sometimes a function of degree at most $d$. In many contexts, the difference is immaterial. For example, a graph of maximum degree 3 on $n$ vertices has at most $1.5n$ edges – and this holds for both meanings.

If the difference is pertinent, then one would hope that you could tell which meaning is intended from context. For example, if we are trying to understand how large the maximum degree can be under some constraints, then probably we refer to the first meaning; and if we have an inductive argument which removes edges, then we might refer to the second meaning.

$\endgroup$
3
$\begingroup$

Usually when people talk of graphs of maximum degree 3, they mean that the maximum degree is at most three. So no, such a graph must not necessarily contain a vertex of degree 3. Sometimes, these graphs are also known as subcubic.

If the meaning is different from this, the terminology tends to be different as well. For example, a cubic graph is a graph where every vertex has degree (exactly) three, i.e., they are the 3-regular graphs.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.