×

#### Thank you for registering.

One of our academic counsellors will contact you within 1 working day.

Click to Chat

1800-1023-196

+91-120-4616500

CART 0

• 0

MY CART (5)

Use Coupon: CART20 and get 20% off on all online Study Material

ITEM
DETAILS
MRP
DISCOUNT
FINAL PRICE
Total Price: Rs.

There are no items in this cart.
Continue Shopping
```
hello formula for finding no of trees in a network graph??
hello
formula for finding no of trees in a network graph??

```
10 years ago

SAGAR SINGH - IIT DELHI
879 Points
```							Dear student,
A network is a collection of points, called vertices, and a collection of lines, called arcs, connecting these points.  A network is traversable if you can trace each arc exactly once by beginning at some point and  not lifting your pencil from the paper.  The problem of crossing each  bridge exactly once reduces to one of traversing the network  representing these bridges.
Euler made the remarkable discovery that whether a  network is traversable depends on the number of odd vertices.  In the  Königsberg network, there are an odd number of arcs at point A, so A is called an odd vertex.  If the number of arcs meeting at a point is even, the point is called an even vertex.  Euler found that the only traversable networks are those that have either no odd vertices or exactly two odd vertices.   Since the Königsberg network has four odd vertices, it is not  traversable.  Therefore, it is not possible to take a walk over the  bridges of Königsberg and cross each bridge only once.

All the best.
Win exciting gifts by                     answering the questions on Discussion Forum. So help         discuss     any       query   on askiitians forum and become an    Elite      Expert   League      askiitian.

Sagar Singh
B.Tech, IIT Delhi

```
10 years ago
Think You Can Provide A Better Answer ?

## Other Related Questions on Discuss with colleagues and IITians

View all Questions »

### Course Features

• 728 Video Lectures
• Revision Notes
• Previous Year Papers
• Mind Map
• Study Planner
• NCERT Solutions
• Discussion Forum
• Test paper with Video Solution

### Course Features

• 731 Video Lectures
• Revision Notes
• Test paper with Video Solution
• Mind Map
• Study Planner
• NCERT Solutions
• Discussion Forum
• Previous Year Exam Questions

Post Question