Intereting Posts

Is it possible for a quadratic equation to have one rational root and one irrational root.
Simplify $\left({\sum_{k=1}^{2499}\sqrt{10+{\sqrt{50+\sqrt{k}}}}}\right)\left({\sum_{k=1}^{2499}\sqrt{10-{\sqrt{50+\sqrt{k}}}}}\right)^{-1}$
Infinite dimensional intermediate subfields of an algebraic extension of an algebraic number field
Image of open set through linear map
Prove that $\sum_{i=0}^{63}f_{i}\cdot\left(n+i\right)^{5}=0$
Sum of the reciprocal of sine squared
A simple explanation of eigenvectors and eigenvalues with 'big picture' ideas of why on earth they matter
How do you compute negative numbers to fractional powers?
Not lifting your pen on the $n\times n$ grid
Derivative of cross-product of two vectors
What is the simplest way to fathom the Monster Group?
Solving two-dimensional recurrence relations
How can I write the Axiom of Specification as a sentence?
Two definitions of Jacobson Radical
A form of cumulative distribution

Here’s what I’m reading: every regular bipartite graph has a 1-factor.

But I understand that not every regular graph has a 1-factor.

So, I was thinking if it’s possible to find a $k$-regular simple graph without 1-factor for any fixed $k$?

- Uses of the incidence matrix of a graph
- What is the number of bijections between two multisets?
- On the eigenvalues of “almost” complete graph ?!
- The Adjacency Matrix of Symmetric Differences of any Subset of Faces has an Eigenvalue of $2$…?
- How to count the no. of distinct ways in which $1,2,…,6$ can be assigned to $6$ faces of a cube?
- Trees that are isomorphic to a subgraph of a graph G.

- Connecting a $n, n$ point grid
- Sentences in first order logic for graphs
- Cayley graphs on small Dihedral and Cyclic group
- Finding the spanning subgraphs of a complete bipartite graph
- Difference between a sub graph and induced sub graph.
- Why can't reachability be expressed in first order logic?
- Prove that a graph $G$ is a forest if and only if every induced subgraph of $G$ contain a vertex of degree at most $1$
- Euler, Grinberg,… who's next?
- Prove that a graph with the same number of edges and vertices contains one cycle
- Prove that every 8-regular graph has 4-and 2-regular spanning subgraph!

If $k$ is even, then $K_{k+1}$ is $k$ regular with $k+1$ (odd) vertices, and hence has no $1$-factor (as a perfect matching requires an even number of vertices).

If $k$ is odd, consider the following graph. Start at an initial vertex, then branch out in $k$ directions. From each of those new vertices, branch out $k-1$many times. For each collection of $k-1$ vertices, draw another $k-1$ vertices opposite it, and connect each vertex on one side with every vertex on the other. Lastly, since $k-1$ is even, in the opposite $k-1$ collection, pair up each vertex with one other vertex. Note that: the initial vertex has $k$neighbors, each ensuing vertex has $k$ neighbors. Every vertex in the first $k-1$ collection is connected to the one that preceeded it and $k-1$ other ones in the matching $k-1$ set, so has $k$ neighbors. Lastly, each vertex in the $k-1$ matching set is connected to every vertex in the initial $k-1$ set, and one more. Thus our graph is $k$ regular. However, if we delete the initial vertex, each component has

$$(k-1) + (k-1) + 1 = 2k – 1$$

vertices, which is an odd number, and so we get $k$ odd components. By Tutte’s theorem, this means that our graph could not have had a $1$-factor.

Here is an illustrative drawing in the $5$ case:

It is possible to have a $k$-regular (simple) graph with no 1-factor for each $k \gt 1$ (obviously in the trivial case $k=1$ the graph itself is a 1-factor).

For $k$ even the complete graph on $k+1$ nodes is an example, since there are an odd number of nodes (and a 1-factor or *perfect matching* implies an even number of nodes).

Petersen showed that any 3-regular graph with no cut-edge has a 1-factor, a result that has been generalized and sharpened. However a 3-regular graph on 16 nodes (connected but not (vertex) 1-connected) is shown in Figure 7.3.1 of this book chapter, about 3/4ths of the way through.

A construction for $k$ odd that generalizes this (connected but not 1-connected) approach is described in a MathHelpForum post. A central vertex $v^*$ has $k$ copies of a certain odd-order (number of nodes) graph connected to it, say $G_1,\ldots,G_k$. In any perfect matching, some edge for $v^*$ must be chosen, its removal leaving some components with odd-order (in which a perfect matching becomes impossible).

- Why squaring the trigonometric equation changes the solution?
- Between bayesian and measure theoretic approaches
- Let $G$ group of order $pq$ where $p,q$ primes.Show that if $G$ contains normal groups $N$ and $K$ with $|N|=p$ and $|K|=q$ then is cyclic
- Prove that the derivative of an even differentiable function is odd, and the derivative of an odd is even.
- Prove that for any element $b$, $|b|$ divides $|a|$ (order of $b$ divides order of $a$).
- Show that ${(F_n^2+F_{n+1}^2+F_{n+2}^2)^2\over F_{n}^4+F_{n+1}^4+F_{n+2}^4}=2$
- Splitting of the tangent bundle of a vector bundle
- Deriving the addition formula for the lemniscate functions from a total differential equation
- Proof that Pi is constant (the same for all circles), without using limits
- Why does $\arctan(x)= \frac{1}{2i}\log \left( \frac{x-i}{x+i}\right)+k$?
- Connectedness problem: sequences of points with distances at most $\varepsilon$
- estimate population percentage within an interval, given a small sample
- Lower hemicontinuity of the intersection of lower hemicontinuous correspondences
- Prove that if $\int_{a}^{b} f(x)$ exists, $\delta >0 $ such that $|\sigma_1 -\sigma_2|<\epsilon$
- Proof of triangle inequality