Show that there is only one positive integer k such that no graph contains exactly k...

Show that there is only one positive integer k such that no graph contains exactly k spanning trees.

Expert Solution

Show that there is only one positive integer k such that no graph contains exactly k spanning trees. I feel that k is 2. And we can show by induction that it is true for k>=3k>=3.

By graph we mean a connected undirected graph.

Look at the kk-th regular polygon, k≥3k≥3. It has kk nodes and kk edges, its spanning tree is all the edges minus one. It has exactly kk spanning trees.
Adding some edges and nodes to a graph won't reduce its number of spanning trees.
A graph has exactly one spanning tree iff it is a tree (un-cyclic), otherwise it has a cycle of length k≥3k≥3, and by the preceding, it has at least kk spanning trees.
For Better understanding see the below information:-
I assume you mean simple graphs, not true for multi-graphs.

The union of the two spanning trees contains a cycle (contains too many edges to be a tree), cycles have length greater than 22. Removing any edge from a cycle leaves a connected graph, so the union of the two spanning trees has at least 33 spanning trees, each of which is a spanning tree for the original graph.

Colby Messinger answered 2 years ago

Show that a graph with at least 2k vertices is k-connected if and only if for...

Show that a graph with at least 2k vertices is k-connected if and only if for any two unrelated subsets X, Y of V, such that | X | = k = | Y |, there are k foreign paths between X and Y.

Given a positive integer k and an array A[1..n] that contains the quiz scores of n...

Given a positive integer k and an array A[1..n] that contains the quiz scores of n students in ascending order, design a divide and conquer algorithm to efficiently count the number of students that have quiz scores in (100(i − 1)/k, 100i/k] for integers 1 ≤ i ≤ k. Let group i be the set of students with quiz scores in (100(i − 1)/k, 100i/k] for integers 1 ≤ i ≤ k. The counting result should be stored in G[1..k],...

Show that an integer is divisible by 17 if and only if the integer formed by...

Show that an integer is divisible by 17 if and only if the integer formed by subtracting 5 times the last digit from the integer formed from the remaining digits is divisible by 17. [For example 442 is divisible by 17 since 44 – 5*2 = 34 is divisible by 17] course: discrete structure

Let k be an integer satisfying k ≥ 2. Let G be a connected graph with...

Let k be an integer satisfying k ≥ 2. Let G be a connected graph with no cycles and k vertices. Prove that G has at least 2 vertices of degree equal to 1.

We say a graph is k-regular if every vertex has degree exactly k. In each of...

We say a graph is k-regular if every vertex has degree exactly k. In each of the following either give a presentation of the graph or show that it does not exist. 1) 3-regular graph on 2018 vertices. 2) 3-regular graph on 2019 vertices.

Let x be a fixed positive integer. Is it possible to have a graph G with...

Let x be a fixed positive integer. Is it possible to have a graph G with 4x + 1 vertices such that G has a vertex of degree d for all d = 1, 2, ..., 4x + 1? Justify your answer. (Note: The graph G does not need to be simple.)

A positive integer N is a power if it is of the form q^k, where q,...

A positive integer N is a power if it is of the form q^k, where q, k are positive integers and k > 1. Give an efficient algorithm that takes as input a number N and determines whether it is a square, that is, whether it can be written as q^2 for some positive integer q. What is the running time of your algorithm? write the pseudocode for the algorithm.

Given an integer array sorted in non-decreasing order, there is exactly one integer in the array...

Given an integer array sorted in non-decreasing order, there is exactly one integer in the array that occurs more than 25% of the time. Return that integer. Input: arr = [1,2,2,6,6,6,6,7,10] Output:

6. Let t be a positive integer. Show that 1? + 2? + ⋯ + (?...

6. Let t be a positive integer. Show that 1? + 2? + ⋯ + (? − 1)? + ?? is ?(??+1). 7. Arrange the functions ?10, 10?, ? log ? , (log ?)3, ?5 + ?3 + ?2, and ?! in a list so that each function is big-O of the next function. 8. Give a big-O estimate for the function ?(?)=(?3 +?2log?)(log?+1)+(5log?+10)(?3 +1). For the function g in your estimate f(n) is O(g(n)), use a simple function g...

Prove that for an integer k, k2 + 4k + 6 is odd if and only...

Prove that for an integer k, k2 + 4k + 6 is odd if and only if k is odd.

Question