Proof for variation of Prim's and Kruskal's to find maximum-weight acyclic subgraph I have been scratching my head to find good counter examples to the following problem:


  Suppose we are given a directed graph G=(V,E) in which every edge has
  a distinct positive edge weight. A directed graph is acyclic if it has
  no directed cycle. Suppose that we want to compute the maximum-weight
  acyclic subgraph of G (where the weight of a subgraph is the sum of
  its edges' weights). Assume that G is weakly connected, meaning that
  there is no cut with no edges crossing it in either direction.
  
  Here is an analog of Prim's algorithm for directed graphs:
  Start from
  an arbitrary vertex s, initialize S={s} and F=∅.
  While
  S≠V, find the maximum-weight edge (u,v) with one endpoint in S and one endpoint in V−S. Add this edge to F, and add the appropriate endpoint to S.
  
  Here is an analog of Kruskal's algorithm. Sort the edges from highest
  to lowest weight. Initialize F=∅. Scan through the edges; at each
  iteration, add the current edge i to F if and only if it does
  not create a directed cycle.


Both algorithm fail.
There should be a 4 vertices graph with 2 cycles that demonstrate this.  

So far I played with different weights for this:

A&lt;----B
^⟍    ^
|  ⟍  |
|    ➘|
C&lt;--- D


However I am not yet able to prove that both algorithms fail.
I would love any suggestioin
This is a nice exercise.  You should probably do it yourself, to get the learning benefit.  I suggest that you enumerate all non-isomorphic graphs with 3 vertices or 4 vertices, and for each such graph, try playing with the weights to try to find a counter-example.  Basically, keep trying what you've been doing, but be more systematic and exhaustive about it.  You're on the right direction -- keep at it.