Intereting Posts

Is a map with invertible differential that maps boundary to boundary a local diffeomorphism?
How to determine a set of polynomials is algebraically indepedent or not?
How are the Taylor Series derived?
Given a joint characteristic function, find $P(X<Y)$
problem books in functional analysis
Intersection of cyclic subgroups: $(x^m) \cap (x^n) = (x^{lcm(m,n)})$
Numbering edges of a cube from 1 to 12 such that sum of edges on any face is equal
Proof that determinant rank equals row/column rank
Prove or disprove that ${F_{n}}^2 + 41$ is always a composite
Find the sum of all 4-digit numbers formed by using digits 0, 2, 3, 5 and 8?
Why do both sine and cosine exist?
How to prove the inequality between mathematical expectations?
Showing $\int_{0}^{\infty} \frac{\sin{x}}{x} \ dx = \frac{\pi}{2}$ using complex integration
union of two independent probabilistic event
Maximum of $|(z-a_1)\cdots(z-a_n)|$ on the unit circle

Every ${K}_{1, 3}$-free connected graph of even order has a perfect matching.

Probably it can be shown using the *Tutte theorem about perfect matching*.

- A graph problem
- Need a counter example for cycle in a graph
- Show that there's a minimum spanning tree if all edges have different costs
- Generating function for planted planar trees
- Graph with 10 nodes and 26 edges must have at least 5 triangles
- Graph theory software?

- Hamiltonian Path Detection
- Prove that a strongly connected digraph has an irreducible adjacency matrix?
- Good way to learn Ramsey Theory
- Integral identity graphs — smallest example
- A game on a smaller graph
- how to determine if two graphs are not isomorphic
- Connected graph with minimum distance
- if $G$ has a matching with $k$ edges, then it has a bipartite subgraph with $(|E(G)+k|)/2$ edges or more
- Is there a nodeless graph?
- All tree orders are lattice orders?

We want to prove that if $G$ has no perfect matching, then it contains the claw. Suppose $G$ has no perfect matching. A strengthening of Tutte’s theorem, the Gallai-Edmonds theorem, allows us to take $S \subset G$ such that:

- $o(G \setminus S) – |S|$ be maximal and
- $S$ is matchable to the components of $G \setminus S$.

We will induct on the order of $S$.

If $|S| = 1$, then $o(G \setminus S) \ge 3$, since $o(G \setminus S) > |S|$ and $o(G \setminus S)$ must be odd since $|G|$ is even. There is an edge from $v \in S$ to all $3$ components, thus providing an example of the claw.

Now suppose $|S| = n+1$ and that the statement holds for $n$. Select $v_1 \in S$ adjacent to exactly two odd components $C_1$ and $C_2$. If it is adjacent to $3$, then we have an example of a claw. $G$ is connected, so we may find $v_2$ with an edge to one of $C_1$ and $C_2$ (let $v_2 c$ be an edge, with $c \in C_1$, without loss of generality).

Now, let $S^* = S – v_1$. We will show that $S^*$ satisfies our induction hypothesis:

- $o(G \setminus S^*) – |S^*|$ is still maximal: $C_1 \cup \{ v_1 \} \cup C_2$ is an odd component of $G \setminus S^*$ and all other components are preserved.
- Moreover, $S^*$ is still matchable to $G \setminus S^*$, since $v_2 c \in E$.

- Need Help: Any good textbook in undergrad multi-variable analysis/calculus?
- C*-algebras as Banach lattices?
- How to solve cubic equations with given coefficients?
- Continuity together with finite additivity implies countable additivity
- Converting from NFA to a regular expression.
- Does every Noetherian domain have finitely many height 1 prime ideals?
- Show that $R/I\otimes_R R/J\cong R/(I+J)$
- Prove that $x^{2} \equiv 1 \pmod{2^k}$ has exactly four incongruent solutions
- Show that $\sqrt{4+2\sqrt{3}}-\sqrt{3}$ is rational using the rational zeros theorem
- Show that there exist only $n$ solutions
- Solve $x^3 +1 = 2y^3$
- What is the difference between $d$ and $\partial$?
- Convergence of double series $\sum_{n=1}^{\infty} \sum_{m=1}^{\infty} \frac{\sin(\sin(nm))}{n^2+m^2}$
- More than 99% of groups of order less than 2000 are of order 1024?
- Does $A^{-1}A=G$ imply that $AA^{-1}=G$?