0
$\begingroup$

Given a graph with n vertices and n edges such that every vertex connect to exactly one other vertex, but there can be many vertices that connect to the same vertex.

So the out degree of every vertex is exactly 1, while the in degree ranges from 0 to n-1.

Another property is that in every graph there can't be a vertex that isn't connected to any other vertex. Therefore for n = 4, we could have graphs where all 4 vertices are connected, and graphs where 2 vertexes are connected, and so on: n = 3 -> (3, 0) n = 4 -> (2, 2), (4, 0) n = 5 -> (2, 3), (5, 0) n = 6 -> (2, 2, 2), (4, 2), (3, 3), (6, 0)

is there a way to count those graphs for an arbitrary n? For example for n = 4 there are 3 (2, 2) graphs and 78 (4, 0) graphs.

$\endgroup$
  • $\begingroup$ Sorry, what do you denote by $(n,m)-$ graph? I am quite confused with those tuples. $\endgroup$ – Phicar Nov 16 '16 at 2:06
  • $\begingroup$ with a (2, 2) graph I mean a graph with 4 vertexes which consists of two subgraphs of 2 vertexes which are connected. $\endgroup$ – ph0t3k Nov 16 '16 at 12:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.