Jesli dobrze rozumiem potrzebujesz dowiedziec sie dla zadanej pary wierzcholkow ile krawedzi musi zostac usunietych, zeby graf rozspojnic, prawda? Jesli o to chodzi, to zagadnienie to mozna rozwiazac korzystajac z twierdzenia
http://en.wikipedia.org/wiki/Max-flow_min-cut_theorem . W skrocie mowi ono, ze minimalna liczba krawedzi potrzebna do rozspojenia grafu jest rowna maksymalnemu przeplywowi w grafie. W Twoim przypadku zapewne warto ustawic przeplyw na wszystkich krawedziach na 1 i zastosowac jakis algorytm do liczenia maksymalnego przeplywu. Na poczatek, jesli nie miales nigdy stycznosci z problemem polecam algorytm forda fulkersona, bo jest to chyba najprostszy algorytm dotyczacy problemu maksymalnego przeplywu:
http://en.wikipedia.org/wiki/Ford%E2%80%93Fulkerson_algorithm . Jesli udalo mi sie rozwiac Twoje watpliwosci, to sie ciesze :) Jesli nie, to pytaj dalej