patternMinor
Graphs of maximum degree three
Viewed 0 times
threedegreegraphsmaximum
Problem
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
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
Solution
In general it is impossible to tell. When people say that a graph has maximum degree 3, they could mean two different things:
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.
- 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.
Context
StackExchange Computer Science Q#109761, answer score: 4
Revisions (0)
No revisions yet.