Q prove the hypothesis that a tree having m nodes has, Ask an Expert

Engineering

Q. Prove the hypothesis that "A tree having 'm' nodes has exactly (m-1) branches".

Ans:

A tree having m number of nodes has exactly (m-1) branches

Proof: A root in a tree has indegree zero and all other nodes have indegree one. There must be (m-1) incoming arcs to the (m-1) non-root nodes. If there is any other arc, this arc must be terminating at any of the nodes. If the node is root, then its indegree will become one and that is in contradiction with the fact that root always indegree zero. If the end point of this extra edge

is any non-root node then its indegree will be two, which is again a contradiction. Hence there cannot be more arcs. Therefore, a tree with m vertices will have exactly (m-1) edges.

View complete question

Computer Engineering, Engineering

Category:- Computer Engineering
Reference No.:- M9504085

Have any Question?Write your Review or question?

Related Questions in Computer Engineering

Java program that does the following please use simple

Java program that does the following: Please use simple computer syntax. More easy to understand! Use a while loop to prompt the user to enter 10 rain falls. Calculate and output the total and the average rain fall. Find ...

Systems analysis project personal trainer inc owns and

Systems analysis project Personal Trainer, Inc. owns and operates fitness centers in a dozen Midwestern cities. The centers have done well, and the company is planning an international expansion by opening a new "superce ...

Nfs allows the file system on one linux computer to be

NFS allows the file system on one Linux computer to be accessed over a network connection by another Linux system. Discuss the security vulnerabilities of NFS in networked Linux systems, and possible mitigation solutions ...

You are requested to design an information technology

You are requested to design an Information Technology Infrastructure for an international nonprofit organization. The organization has six offices, one each in Ohio, Kentucky, Toronto, Michigan, Chicago, and Indiana. Col ...

Suppose a coworker approaches you and asks what an ethical

Suppose a coworker approaches you and asks what an ethical hacker does. She does not understand the role that an ethical hacker plays in the security industry and assumes that such a hacker intentionally causes damage. E ...

In a random sample of 100 male students 80 reported that

In a random sample of 100 male students, 80 reported that they were in favour of writing announced tests, while in a sample of 50 female students 23 favoured writing announced tests. Let the male students be population 1 ...

A biostatistician is investigating the timenbspt to death

A biostatistician is investigating the time, T , to death of a mouse exposed to a newly developed pesticide. He finds that the pdf of T is given by the following formula f(t) = 15t 2 e -5t3 . Which of the following sta ...

Given an undirected graph with both positive and negative

Given an undirected graph with both positive and negative edge weights, design an algorithm to find a maximum spanning forest with the largest total edge weights.

Question suppose direction is an integer angle between 0

Question : Suppose direction is an integer angle between 0 and 359 degrees. You turn by a given angle and update the direction as direction = (direction + turn) % 360; In which situation do you get the wrong result? How ...

Take a position on whether user interfaces for work will

Take a position on whether user interfaces for work will remain isolated or become more collaborative. Present evidence, based on the different categories of social media, to support your argument. Include at least two r ...

4,153,160 Questions Asked
13,132 Experts
2,558,936 Questions Answered

Ask Experts for help!!

Looking for Assignment Help?

Start excelling in your Courses, Get help with Assignment

Write us your full requirement for evaluation and you will receive response within 20 minutes turnaround time.

Ask Now Help with Problems, Get a Best Answer

Recent Questions

Ask Computer Engineering Expert