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.

Solutions

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 1 year ago

Next > < Previous

Related Solutions

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.

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.)

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.

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.

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.

Given that the square matrix, A is nilpotent (Ak = 0 for some positive integer k)....

Given that the square matrix, A is nilpotent (Ak = 0 for some positive integer k). If A is n by n, show that An = 0.

Show a complete graph for both of these shocks. You will need two graphs only, one...

Show a complete graph for both of these shocks. You will need two graphs only, one for each shock. The graphs have to show: -The new short run equilibrium immediately after the shock occurs. -The new long run equilibrium. -The transition to the long run equilibrium. Properly label your axes and the curves in your graphs, and use arrows to show shifts of curves and the change in the price level and output. The two shocks are: The stock market...

Subjects