Perfect Matching in a non-bipartite graph

Question

I need to find out if you can have a perfect matching in a given graph, with $n$ vertices and $m$ edges and $1\leq n,m\leq 100$. I want a complexity of $O(n)$ if possible. I only need to know if there is such a perfect matching, not its composition.

Answer 1

Check out the bounds on the wiki page. An existence algorithm is given here, but I don't know how much that buys you.

Answer 2

Edmonds matching algorithm runs in $O(n^4)$. It is relatively easy to understand (I think). The Wikipedia page says that the paper 'An $O(V^{1/2}E)$ algorithm for finding maximum matching in general graphs' can do it in $O(\sqrt VE)$, but since (usually) $E=O(V^2)$, it is about $O(V^{\frac 52})$. I can't find that article on google right now. When I find it, I'll post a link. Here is a paid one.
EDIT: And this seems to be a free version.

To know whether or not a perfect matching exists is usually just as hard as finding one. If you know your graph is $K_n$ or some other strong fact about it, it may be easy to prove. Otherwise, you will have to search for one.