let degree graph f =
    let n = (G.nb_vertex graph) in
    let m = ref 0 in
    let h = Hashtbl.create 1031 in
    let add h v =
      (* we don't care about leaves *)
      if v = 0 then () else
      try Hashtbl.replace h v ((Hashtbl.find h v) + 1)
      with Not_found -> Hashtbl.add h v 1
    in
    let total = 
      G.fold_vertex (fun v sum ->
        let s = (List.length (f graph v)) in
        if s > !m then m := s ;
        add h s ;
        sum + s
      ) graph 0
    in
    ( (float_of_int total) /. (float_of_int n) , !m, h)