For one of my algorithms, i'm looking to know what are the graphs that have only three degree vertex.
For example here is the first graph i know, that have this property:
graph example with only 3 degree vetices
Are they other graph instances that have this criterion?
Thank you.
If such a graph has $V$ vertices and $E$ edges then
$2E = 3V$
so $V$ must be a multiple of $2$ and $E$ must be a multiple of $3$.
Draw two cyclic graphs, each with $n$ vertices. Each vertex has degree $2$. Now create a one-to-one mapping between the vertices in one cycle and the vertices in the other cycle. Add edges linking each vertex in one cycle to the corresponding vertex in the other cycle. Now you have a graph with $2n$ vertices and $3n$ edges where each vertex has degree $3$.