Intereting Posts

Number of ways to write set $S$ as union of $l$ unique $k$-subsets
Prove -n^2 diverges to negative infinity
What precisely is a vacuous truth?
To find the minimum of $\int_0^1 (f''(x))^2dx$
Don't understand casting out nines
Proof involving norm of an integral
Is there a bounded function $f$ with $f'$ unbounded and $f''$ bounded?
Let $a,b \in \mathbb{Q^{+}}$ then $\sqrt{a} + \sqrt{b} \in \mathbb{Q} $ iff $\sqrt{a} \in \mathbb{Q}$ and $\sqrt{b} \in \mathbb{Q}$
If $\gcd(a, b) = 1$ and if $ab = x^2$, prove that $a, b$ must also be perfect squares; where $a,b,x$ are in the set of natural numbers
Estimating $\sum n^{-1/2}$
Type of singularity of $\log z$ at $z=0$
Why are the fundamental theorems of calculus usually associated to the Riemann Integral?
The Relation between Holder continuous, absolutely continuous, $W^{1,1}$, and $BV$ functions
Proof for $A \cup B = B$ if and only if $A \subset B$
Can an algebraic extension of an uncountable field be of uncountable degree?

Can someone please verify this?

Show that a connected graph on $n$ vertices is a tree if and only if it has $n-1$ edges.

$(\Rightarrow)$ If a tree $G$ has only $1$ vertex, it has $0$ edges. Now, assume that any tree with $k-1$ vertices has $k-2$ edges. Let $T$ be a tree with $k$ vertices. Remove a leaf $l$ to obtain a tree $T’$ with $k-1$ vertices. Then, $T’$ has $k-2$ edges, by the inductive hypothesis. The addition of $l$ to $T’$ produces a graph with $k-1$ edges, since $l$ has degree $1$.

- Does this explanation of derangements on Wikipedia make sense?
- What is the $m$th derivative of $\log\left(1+\sum\limits_{k=1}^N n_kx^k\right)$ at $x=0$?
- Subsets with small interaction.
- Combinatorics question about english letters (with consonants and vowels)
- Combinatorial Identity $(n-r) \binom{n+r-1}{r} \binom{n}{r} = n \binom{n+r-1}{2r} \binom{2r}{r}$
- Deriving the formula for the Möbius function?

$(\Leftarrow)$ Let $G$ be a connected graph on $n$ vertices, with $n-1$ edges. Suppose $G$ is not a tree. Then, there exists at least one cycle in $G$. Successively remove edges from cycles in $G$ to obtain a graph $G’$ with no cycles. Then, $G’$ is connected and has no cycles. Therefore, $G’$ is a tree, with $n$ vertices and $n-1-x$ edges, for some $x > 0$. However, this contradicts the previous derivation. Therefore, it must be the case that $G$ is a tree.

- Vandermonde identity corollary $\sum_{v=0}^{n}\frac{(2n)!}{(v!)^2(n-v)!^2}={2n \choose n}^2$
- # of counts of an element - Combinatorial Proof of Inclusion-Exclusion Principle (IEP)
- Combinatorics-N boys and M girls are learning acting skills from a theatre in Mumbai.
- Why is $S_5$ generated by any combination of a transposition and a 5-cycle?
- Number of ways to express a number as the sum of different integers
- Finding $\binom{999}{0}-\binom{999}{2}+\binom{999}{4}-\binom{999}{6}+\cdots +\binom{999}{996}-\binom{999}{998}$
- Combining stones into one stack
- Proving identity $ \binom{n}{k} = (-1)^k \binom{k-n-1}{k} $. How to interpret factorials and binomial coefficients with negative integers.
- Two disjoint spanning trees, spanning subgraph with all even degrees
- A closed form for $T_N = 1 + \sum\limits_{k=0}^{N-2}{(N-1-k)T_k}$?

The proofs are correct. Here’s alternative proof that a connected graph with n vertices and n-1 edges must be a tree modified from yours but without having to rely on the first derivation:

Let $G$ be a connected graph on n vertices, with n−1 edges. Suppose $G$ is not a tree. Then, there exists at least one cycle in $G$. Remove one of the edges within a cycle. This leaves a connected graph on n vertices with n-2 edges which is impossible as a connected graph on n vertices must at least have n – 1 edges.

Yes, this seems like it is true, although you didn’t prove a leaf must always exist, if you really want to be rigorous. And in the other part you didn’t explain why if it contained a cycle you could remove an edge without the graph being disconnected, but I like the proof over all.

I have the following way of proving it. Let me know if you agree with it or not.

Suppose the graph on $n$ vertices with $n-1$ edges is not a tree. This implies it has at least $1$ polygon. Suppose in total there are $k$ edges involved in these polygons and we know that a polygon has as many edges as vertices, since polygons are of regular degree 2. Then, if we consider th egraph without the edges that form the polygons, then we have a connected graph with at least $n-k$ edges, since in a connected graph every vertex has degree at least 1. Thus, in total this would imply we have at least $n$ in all the graph. But this contradicts the fact that we have $n-1$ in the original graph. Thus it must be a tree.

- If $R$ is a commutative ring with identity, and $a, b\in R$ are divisible by each other, is it true that they must be associates?
- Uniform convergence of Taylor series
- Arbitrage sports betting
- confusion regarding compactness theorem
- How many groups of order $512$ and $1024$ are there with a center of size $2$?
- Show that $f_k'(z)=z^{k-1}$ does not converge uniformly for $|z|<1$.
- Locally or Globally Lipschitz-functions
- Half Exact Functor
- Proving if $a$ is not a multiple of prime $p$, then an integer $b$ exists such that $p^b – 1$ is a multiple of $a$
- Prove $\frac{|a+b|}{1+|a+b|}<\frac{|a|}{1+|a|}+\frac{|b|}{1+|b|}$.
- Integral of bounded continuous function on $R$
- Show that $\int_0^\infty\frac{1}{1+x^n}\,\mathrm dx = \frac{\pi/n}{\sin(\pi/n)}$ for $\mathbb{N}\ni n\geq 2$
- Proving $\sqrt2$ is irrational
- Existence of solutions to diophantine quadratic form
- Representations of integers by a binary quadratic form