I know that we can check existence of cycle in graph by simply traversing the graph and check whether the vertex has been visited.
However, if there are only number of vertices and their corresponding degree known, can we check if the graph contains at least a cycle?
Provided that there is no self-loop and no cycle involving exactly only 2 vertices with 2 degrees each. So it doesn't matter how they are connected to each other.
Is that possible without first randomly connecting each vertex according to the their degrees and then traversing the graph?
Edit
Actually the problem is to find a maximum value from a set of vertices if the vertex connected to other vertex. So let say I'm provided with a set of number $M$ and $|M| = |V| – 1$ with $V$ being a set of vertices, $M_n$ being the value that a vertex can have if the vertex is connected to $n$ other vertices (degree).
Eg.
$$M = (4, 1, 1, 3, 2)$$
In that case the $|V|=6$ and let say $V=(V_1,….,V_6)$.
That means if any of those vertices is connected to a vertex the value of both vertices would be $4$ ($M_1=4$, degree = 1) but if connected to other 3 vertices the value of that particular vertex would be $1$ ($M_3=1$, degree = 3).
From that, I'd like to find which combination yields the most value without introducing a cycle in the graph.
At first I was thinking of trying each combination one-by-one and constructing a graph from each combination then look for a cycle. However that approach wouldn't be feasible if there are a lot of vertices. So now I'm thinking of sorting the degree ($n$) first by the value ($M_n$) then start from there and thinking if it'd be possible to detect a cycle without constructing a graph.
Best Answer
If you have an $n$-vertex graph with $n$ or more edges, there must be a cycle. You can calculate the number of edges from the degree sequence using the Handshaking Lemma.
If the $n$-vertex graph has $n-1$ or fewer edges, provided there are two vertices of degree $2$ or more, it may contain a cycle (or it may not). For example, these two graphs have the same degree sequences but only the first one has a cycle:
If you also knew the number of components $c(G)$ of the graph $G=(V,E)$ you could determine whether or not there is a cycle. Specifically, a graph is acyclic if and only if $c(G)=|V|-|E|$.