Intereting Posts

Classifying complex conics up to isomorphism as quotient rings of $\mathbb{C}$
Are there real numbers that are neither rational nor irrational?
How do I calculate $\lim_{x\to+\infty}\sqrt{x+a}-\sqrt{x}$?
Reference for Lie-algebra valued differential forms
Characteristic 2
What is the definition of an “almost complete” order?
How have I incorrectly calculated the area A inside the curve $r =1$ and outside the curve $r = 2\cos(\theta)$
''Linear'' transformations between vector spaces over different fields .
Existence of an injection from $\Bbb N$ without the axiom of choice
Prove that the dihedral group $D_4$ can not be written as a direct product of two groups
Find possible number of triangles with integer sides for a given inradius
Is the Pythagorean closure of $\mathbb Q$ equal to the field of constructible numbers?
Problem on $\operatorname{Hom}(\mathbb Z_6,R^*\oplus C^*)$
Proof of $\sqrt{n^2-4}, n\ge 3$ being irrational
How to find the closed form of 10.3500574150076 with software/algorithm?

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

- Count Eulerian cycles in $K_{n,2}$
- Trees with odd degree sequence
- A graph problem
- How else can we be nauty?
- Euler's Solution of Seven Bridges of Königsberg in Layman Terms
- How to count the closed left-hand turn paths of planar bicubic graphs?

- Radius, diameter and center of graph
- Probabilistic approach to prove a graph theory theorem
- For all $1 \leq i < j \leq k$, the subtrees $T_i$ and $T_j$ have a vertex in common. Show that $T$ has a vertex which is in all of the $T_i$.
- Prove that the chromatic polynomial of a cycle graph $C_{n}$ equals $(k-1)^{n} + (k-1)(-1)^{n}$
- Proving graph connectedness given the minimum degree of all vertices
- Partition edges of complete graph into paths of distinct length
- Prove Dirac's Theorem by induction on the number of vertices
- Maximum number of edges in a planar graph without $3$- or $4$-cycles

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

- Exercise $1.8$ of chapter one in Hartshorne.
- When can Galois theory actually help you find the roots of a polynomial?
- inclusion of $\sigma$-algebra generated by random variables
- Euler's $\phi(n)$ function
- Is there a null sequence that is in not in $\ell_p$ for any $p<\infty$?
- Rubik's Cube Combination
- Why is the fixed field of this automorphism $\mathbb Q(\pi^2)$?
- Differentiation under the integral sign – line integral?
- Confusion on how to solve this question about sequences.
- The range of a continuous function on the order topology is convex
- What exactly are fractals
- Show that the Sorgenfrey line does not have a countable basis.
- Integrating $\int \frac{\sqrt{\cos 2x}}{\sin x} dx$
- $g$ a restriction of a homeomorphic function $f$, $g$ also homeomorphic?
- Is this property sufficient for function $f$ to be continuous?