Discrete Math- Number of factor trees of a graph

1)Find the number of factor trees of the graph below

2)Given the graph G of the figure below. What is the number of factor trees of G that contain the path 2-3-4-5-6-7-11 ?

3)Suppose we want to schedule the courses of the exam period so that there is no student who has two courses on the same day. The data is as follows: we have the courses numbered with numbers 1,2,...,7 and the diagram below which shows if there is a student enrolled in two courses at the same time. More specifically, if there is an asterisk in position i,j, this means that there is a student enrolled in course i and course j at the same time. What is the minimum number of days we need to schedule the exams?

4)Let T be a tree with 20 vertices, for which we know that each vertex has degree either 1 or 4. We want to add to this tree the minimum number of edges possible (without adding extra vertices) so that the resulting graph has an Euler cycle . How many edges should we add?

Pictures down below for each question

  • For a collection of four high level graph theory questions, the offered bounty is low!

  • I just increased it to 45!

  • What class level is this for? Regarding questions 1 and 2, can you elaborate a bit more about the "factor trees of a graph"? Do you mean identifying the prime factors of each vertex (assuming the number on the vertex) in the graph provided?

  • prime factors of each vertex yes!

  • Let me correct it. It means how many trees can a graph produce with that path

  • Thinking more about it, I think it is asking for the number of spanning trees in the graph. And then for the second question, as you said, how many trees in the graph include that path. Thanks for confirming.


Answers can be viewed only if
  1. The questioner was satisfied and accepted the answer, or
  2. The answer was disputed, but the judge evaluated it as 100% correct.
View the answer

1 Attachment

  • @kratos, just to confirm, I have received a $1 tip. Thanks,. If you intended to leave a higher tip, please use a PC or laptop device. This happened with another user and apparently using mobile phone, the system only allows a $1 tip, no matter what number you put as tip.

The answer is accepted.