retagged by
556 views
3 votes
3 votes

The figure above shows an undirected graph with six vertices. Enough edges are to be deleted from the graph in order to leave a spanning tree, which is a connected subgraph having the same six vertices and no cycles. How many edges must be deleted?

retagged by

1 Answer

6 votes
6 votes
The easiest way to do this is to play around, I think. One, two, or three edges don’t seem to be enough, but removing four edges gives us a straight graph on six vertices.

Note that a connected graph with no cycle is called a tree. $A$ tree on n vertices has $n-1$ edges. We need to delete edges from the given graph so that only $5$ edges remain. Hence, $4$ edges must be deleted.
edited by
Answer:

Related questions

694
views
1 answers
7 votes
GO Classes asked Jan 13
694 views
An MIPS pipeline has five stages, with a clock cycle of $200 \mathrm{ps}$. Suppose that this MIPS pipeline is redesigned to have four stages, with a ... , what speedup will this new design achieve when compared to the five-stage pipeline?
708
views
1 answers
4 votes
GO Classes asked Jan 13
708 views
Consider the bit pattern $10110110.$ Interpret this bit pattern as a $8$-bit $2$'s complement number. What is the largest magnitude negative number that can ... overflow? (Write your answer in decimal, only the magnitude, not the sign)
599
views
1 answers
5 votes
GO Classes asked Jan 13
599 views
If $F$ is a function such that, for all positive integers $x$ and $y, F(x, 1)=x+1, F(1, y)=2 y$, and $F(x+1, y+1)=F(F(x, y+1), y)$, then $F(2,3)=$
584
views
1 answers
3 votes
GO Classes asked Jan 13
584 views
Suppose that $X$ and $Y$ are independent random variables such that each is equal to $0$ with probability $.5$ and $1$ with probability $.5.$Find $P(X+Y \leq 1)?$ (Answer up to $2$ decimals)