[Valmont]

The fact that it runs, is never ever a prove that correct deletion occured!
Convince yourself it is correct indeed.

You can do that by creating a static member which holds the number of allocations on the freestore:

{ ...
public:
   static unsigned EdgeCounter_;
};

//Later...
*stitch = new Edge
++EdgeCounter_; 
//...

Outside the classs:

unsigned Mygraph::EdgeCounter = 0;

And then in the delete function (deletelist())

void Mygraph::deletelist()
{
  Edge *nextedge;
  Edge *doomed;
  for(int i = 0; i < size; i++)
  {
    doomed = vlist[i].edges;
    while(doomed)
    {
      cout<<"deleting..."<<endl;
      nextedge = doomed->nextedge;
      delete doomed;
      cout<<--EdgeCounter_<<endl;
      doomed = nextedge;
    }
  }
//INSERT BREAKPOINT HERE
  delete [] vlist;
}

why would glibc choke on deleting a simply array and linked lists, and then change its mind?

See if you have the latest version.