Detecting connected acyclic through Tarjan strongly connected components variant
I don't think graph algorithms work well with functional programming: you have to track which nodes were already visited and that pretty much requires global mutable state. You can simulate mutable state in a purely functional way by adding a parameter and a return value to the graph-walking function, but that quickly becomes tedious.

Because of that, I think that using imperative F#, or maybe even better, C# is a good choice here.



Your code does not tell you whether the graph is weakly connected, it tells you whether all nodes are reachable from the first node. (I'm assuming you're not interested in strongly connected graphs, because that implies cycles.) For example, given:

let aLine = function
| 0 -&gt; [1]
| 1 -&gt; [2]
| 2 -&gt; [3]
| 3 -&gt; []


Then (kindOfGraph aLine 0 4).connected returns true, while (kindOfGraph aLine 1 4).connected returns false. I don't know whether this is a bug in the code or whether you're misusing the word "connected" to mean something different, I could imagine both being the case.



I don't like that you're representing the graph as a function (plus the first node and size). I think that graph should be a self contained data structure, maybe something like Map&lt;int, int list&gt;.



I don't understand why are you using Tarjan's algorithm here.

To find out whether a graph contains cycles, DFS is enough.

To find whether all nodes are reachable from a specific node, simplified DFS (that doesn't try other starting nodes) will work.

To find whether a graph is weakly connected is more complicated. I think the simplest way would be to convert it to an undirected graph (by adding the reverse of each edge) and then performing DFS on that.



Since you're not actually interested in the connected and acyclic properties separately and since you're aware that your code is not always accurate when it comes to being acyclic, I would return only a single boolean value, not a record with misleading field names.