Fr 0568 # 28

Forum for the GRE subject test in mathematics.
Post Reply
Posts: 17
Joined: Fri Mar 26, 2010 7:18 am

Fr 0568 # 28

Post by thmsrhn » Sat Mar 27, 2010 9:14 am

Damn this paper! Can t even half way through.

Anyways here s another one which i have a problem with.


The figure above shows an undirectede graph with six vertices. Enuff edges are to be deleted from the graph in order to leave a spnning tree, which is a connected sibgraph having the same six vertices and no cycles. How many edgges are to deleted/

1,2,3,4, or 5?

Posts: 61
Joined: Fri Oct 23, 2009 11:42 pm

Re: Fr 0568 # 28

Post by origin415 » Sat Mar 27, 2010 11:37 am

Connected spanning trees always have one less edge than vertex.

Post Reply