## 11597 - Spanning Subtree

Moderator: Board moderators

yiuyuho
A great helper
Posts: 325
Joined: Thu Feb 21, 2002 2:00 am
Location: United States
Contact:

### 11597 - Spanning Subtree

I see that the answer is trivially n/2, but why is that true?

Tausiq
New poster
Posts: 6
Joined: Fri Mar 06, 2009 4:54 pm
Location: just here
Contact:

### Re: 11597 - Spanning Subtree

How many edges are possible if vertex_number = 4 ?
as there is no self-loop, u can draw 6 edges
try this using pen-paper

similarly, when vertex_number = 6,
highest number of edges = 15

Code: Select all

``````int edges = 0;
for ( int i = 1; i <= vertex_number; i++ ) {
for ( int j = i + 1; j <= vertex_number; j++ ) {
edges ++;
}
``````

to form a spanning tree with 6 vertices, we must need 5 edges
its very simple, when there are n vertices
we need at least (n - 1) edges to form a spanning tree

so, Number of vertices = 6
highest number of edges = 15
minimum 5 edges needed to form a spanning tree
eventually, we can form 3 spanning trees (15 / 5)
I took an IQ test .. and the results were negative !

zobayer
Experienced poster
Posts: 110
Joined: Tue May 06, 2008 2:18 pm
Contact:

### Re: 11597 - Spanning Subtree

From combinatorics, it is way too easy to find the required solution. However I am interested if n is odd. Can anyone explain what will happen if n is odd? What I guess is, if n > 3, and n is odd, it is always 2. Is it ok? Find me a path to more of a mathematical proof.
You should not always say what you know, but you should always know what you say.

Shafaet_du
Experienced poster
Posts: 147
Joined: Mon Jun 07, 2010 11:43 am
Contact:

### Re: 11597 - Spanning Subtree

Easy problem. in an complete graph you have n*(n-1)/2 edges and you need n-1 edges to form each spanning tree.

New poster
Posts: 28
Joined: Fri Mar 30, 2012 12:57 am

### Re: 11597 - Spanning Subtree

Hi!
Does anybody know how can I reduce my runtime to zero?
Here is my code:

Code: Select all

``````#include <stdio.h>

int main()
{
int n;
int caseNo = 1;

scanf( "%d", &n );
while ( n != 0 )
{
printf( "Case %d: %d\n", caseNo++, n >> 1 );
scanf( "%d", &n );
}

return 0;
}``````