Check existence of cycle in graph with only number of vertices and their degree
By Sebastian Wright
$\begingroup$
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.
$\endgroup$ 42 Answers
$\begingroup$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|$.
$\endgroup$ 1 $\begingroup$if there are only number of vertices and their corresponding degree known, can we check if the graph contains at least a cycle?
Do you mean a complete cycle (Hamiltonian) or any cycle at all? Vertex degrees fail in some strong ways for the problem of a complete cycle, because degree-based tests are too fast to be able to solve NP-complete problems. To test if there is any cycle is to test whether the graph is a union of trees, which is computationally simple, number of edges = $n$ - (number of connected components), but that is not a local condition that can be determined by degrees of vertices.
A set of vertex degrees forces Hamiltonicity if and only if it satisfies Chvatal's numerical condition (as in the Bondy-Chvatal theorem, ), and non-Hamiltonicity is forced only in trivial situations like not having enough edges to form a complete cycle. Most sets of vertex degrees are consistent both with a Hamilton cycle existing, and with a cycle not existing, so that there is not enough information in the degrees to test for a Hamiltonian cycle. Degree-based tests and other local methods that look only a finite distance away from each vertex have polynomial run-time, but testing Hamiltonicity is NP-complete, which makes local tests hopeless for general graphs.
$\endgroup$![How can I play the content from another account on my new Xbox 360 console? [duplicate]](https://edu.smbbmcl.edu.pk/uploads/how-can-i-play-the-content-from-another-account-on-my-new-xbox-360-console-duplicate_720.jpg)
