Intereting Posts

Given $N$, what is the next prime $p$ greater than $N$?
Can we simplify $\int_0^{\pi}\left(\frac{\sin nx}{\sin x}\right)^mdx$?
Prove that if Rank$(A)=n$, then Rank$(AB)=$Rank$(B)$
Jeep problem variant: cross the desert with as much fuel as possible
Expected value – continuous random variable
Positive harmonic function on $\mathbb{R}^n$ is a constant?
How to evaluate $\int_0^{2\pi} \frac{d\theta}{A+B\cos\theta}$?
Conformal mapping between regions symmetric across the real line
How does this equation to find the radius from 3 points actually work?
Best book on axiomatic set theory.
Show that the set of functions under composition is isomorphic to $S_3$
Initial Segments of Modular Arithmetic
A converse of sorts to the intermediate value theorem, with an additional property
Finite injective dimension of the residue field implies that the ring is regular
Possible mistake in Folland real analysis?

Find the smallest number $x$ so that if an $n$-vertex simple graph has at least $x$ edges then it contains $k$ pairwise edge-disjoint perfect matchings* ($k$ is a positive integer, $n$ is an even number greater than $k$).

*It means you find $k$ matchings which are pairwise edge-disjoint.

- graph theory - clique graph
- 3 Utilities | 3 Houses puzzle?
- Connection Between Automorphism Groups of a Graph and its Line Graph
- 4-Color Theorem on Surfaces
- Why a complete graph has $\frac{n(n-1)}{2}$ edges?
- Proving graph connectedness given the minimum degree of all vertices

- Unique local extremum is absolute extremum for continuous functions
- How many nodes are there in a 5-regular planar graph with diameter 2?
- Cayley graphs on small Dihedral and Cyclic group
- Graph Theory: How quickly will triadic closure create a complete graph?
- Maximal area of a triangle
- Why this graph has automorphism group is isomorphic to the cyclic group of order 4?
- chromatic number of a graph versus its complement
- Prove that a simple planar bipartite graph on $n$ nodes has at most $2n-4$ edges.
- A binary sequence graph
- Prove that the maximum number of edges in a graph with no even cycles is floor(3(n-1)/2)

It is well-known that $K_n$, with ${n \choose 2}$ edges, decomposes into $n-1$ edge-disjoint perfect matchings. Consider a graph $G$ with at least ${n – 1 \choose 2} + k$ edges. $G$ is missing at most $n-1-k$ edges from the complete graph, and each missing edge means we need to throw away at most one of the perfect matchings. Hence we have $n-1 – (n – 1 – k) = k$ edge-disjoint perfect matchings left.

This is best possible, since if we have a graph $G$ that’s a $K_{n-1}$ with an additional vertex incident to $k$ other vertices, it has ${n-1 \choose 2} + k$ edges and at most $k$ perfect matchings.

Here’s an answer for the case $k=1$, perhaps you can build on it. The example $K_{n-1}$ (plus an isolated vertex) shows that $x > {n-1\choose 2}$. Suppose now that $e(G) > {n-1\choose 2}$, so that $e(G^c) < n-1$.

For each edge $e$ in the complement $G^c$, there are $(n-3)!! = (n-3)(n-5)\cdots 1$ perfect matchings of $K_n$ which pass through $e$. But there are $(n-1)!!$ perfect matchings altogether, and since $(n-1)!! > (n-3)!! e(G^c)$, there must be some perfect matching of $K_n$ that does not contain any edge of $G^c$, hence is a subgraph of $G$.

- Prove that $3^{(q-1)/2} \equiv -1 \pmod q$ then q is prime number.
- Find all $n$ for which $n^8 + n + 1$ is prime
- Positive operator is bounded
- Closed form for $\sum_{n=-\infty}^\infty \frac{1}{(z+n)^2+a^2}$
- Suppose that there exist a set $\Gamma$ of positive measure such that $\nabla u=0, a.e.\ x\in\Gamma$.
- A simple proof that $\bigl(1+\frac1n\bigr)^n\leq3-\frac1n$?
- Maximal Ideals in the Ring of Complex Entire Functions
- Do all square matrices have eigenvectors?
- Is this an isomorphism possible?
- Partition the points
- Linear independence of the numbers $\{1,e,e^2,e^3\}$
- $f(x)=x/1$ is not injective?
- $\operatorname{func}(f)\to((x,y)\in f\to f(x)=y) $ and $\operatorname{func}(f)\to((x \in \operatorname{dom}(f) \wedge f(x)=y)\to (x,y)\in f)$
- Check my answer: A slight modification to the 'hat-check' problem.
- Intersection of conjugate subgroups is normal