Cute problem . I hope the following is correct. The hypothesis says that we have $2n+1$ vertices in a graph $G$, and for each vertex $x$ of $G,\ G-x$ has a perfect matching. The conclusion should be that every vertex lies on some odd cycle. Let $x$ be a vertex of $G$, and let $x_1,x_2,\ldots,x_t$ be its neighbours. If we eliminate $x$, the remaining graph has a perfect matching, so let $v_1,\ldots,v_t$ be the neighbours of $x_1,\ldots,x_t$, respectively, in this perfect matching ($2t=n$, of course). Now eliminate $x_1$. The neighbour of $x$ in the new perfect matching we get is one of the $x_i$'s, with $i\ge 2$. Suppose WLOG that it's $x_2$. The remaining vertices are now $x_3,\ldots,x_t$ and $v_1,v_2,\ldots,v_t$, which form a perfect matching. We also have edges between $x_i,v_i,\ \forall i\ge 3$, from the previous perfect matching, when we eliminated $x$. Start from $v_1$, go to its neighbour in the new matching, then to that vertex' neighbour in the old matching, then to this new vertex' neighbour in the new matching, and so on, until you reach $v_2$. We have started with an edge in the new matching, alternating the old matching with the new one, the last edge also being from the new matching, which means tht we have used an odd number of edges. These edges, together with $xx_1,x_1v_1,xx_2,x_2v_2$, form an odd cycle on which $x$ lies.

grobber wrote: Cute problem . I hope the following is correct. The hypothesis says that we have $2n+1$ vertices in a graph $G$, and for each vertex $x$ of $G,\ G-x$ has a perfect matching. The conclusion should be that every vertex lies on some odd cycle. Let $x$ be a vertex of $G$, and let $x_1,x_2,\ldots,x_t$ be its neighbours. If we eliminate $x$, the remaining graph has a perfect matching, so let $v_1,\ldots,v_t$ be the neighbours of $x_1,\ldots,x_t$, respectively, in this perfect matching ($2t=n$, of course). Now eliminate $x_1$. The neighbour of $x$ in the new perfect matching we get is one of the $x_i$'s, with $i\ge 2$. Suppose WLOG that it's $x_2$. The remaining vertices are now $x_3,\ldots,x_t$ and $v_1,v_2,\ldots,v_t$, which form a perfect matching. We also have edges between $x_i,v_i,\ \forall i\ge 3$, from the previous perfect matching, when we eliminated $x$. Start from $v_1$, go to its neighbour in the new matching, then to that vertex' neighbour in the old matching, then to this new vertex' neighbour in the new matching, and so on, until you reach $v_2$. We have started with an edge in the new matching, alternating the old matching with the new one, the last edge also being from the new matching, which means tht we have used an odd number of edges. These edges, together with $xx_1,x_1v_1,xx_2,x_2v_2$, form an odd cycle on which $x$ lies. Grobber, when you say $2t=n$ you are asuming that there are no more vertex, but there could be, implying that in other matchings $x$ need not be conected to some other $x_j$??? I dont now who is wrong but i really don get that part but the other part seems clear....

I've deleted my previous reply, where I was saying that I was too busy to look into this (I actually was very busy ). That $2t=n$ thing makes absolutely no sense. I don't know what I was thinking. Of course, there can be other vertices. However, the neighbour of $x$ in every matching is always one of the $x_i$'s, since those are all its neighbours, so I don't really know what you meant by: Pascual2005 wrote: implying that in other matchings $x$ need not be conected to some other $x_j$??? Another thing that needs to be clarified: I was trying to show that $x$ lies in an odd cycle, so I assumed that none of the $x_i$'s are connected to each other. This means that the $v_i$'s are distinct from the $x_i$'s. I just wanted to point this out, so that there's no confusion. Is it Ok now (the procedure is the same: we construct an alternating path with edges from both the new and old matchings)?

yes it is clear now, that $2t=n$ got me a little confused...but as i told you i understood the rest of the idea...

Here is an overkill.A graph doesn't contain an odd cycle iff it is bipartite(very well known).Now,we can divide our graph $G$ into two groups,$A$ and $B$ such that if two edges are in the same group they don't have an edge beetwen them.Now,since the $G$ has ann odd number of vertices,$A$ and $B$ can't have the same number of vertices,so pick an arbirtary edge from $B$(WLOG $B$ has less elements than $A$) and it is easy to see that we don't have a perfect matching for him,so done. It is pretty strange this problem was in the contest,cause if you heard about bipartite graphs this is very natural and you are done pretty much instant.

No, your solution is completely wrong: "there exists an odd cycle" and "every vertex belongs to an odd cycle" are very different. (This is not ambiguous in the question and is mentioned in the earlier solution as well!)

Ok,I was in a rush so I didn't mention one more thing,the graph is connected.Assume it is not,then we will have $2$ groups $A$ and $B$ so that there isn't any edge from $A$ to $B$.Now,at least one will be odd and that is a contradiction.Now,consider a 'tree' from any vertex(I mean,if we can get to some vertex by minimum $i$ steps then it is at $i+1$-st level) and now color them alternate the starting vertex black,the vertices at the second level(its neighbours white) etc.Now,if we don't have an edge which vertex isn't the same colour we have a bipartite graph so contradiction,if not then we will have an odd cycle which contains our starting vertex.As JBL mentioned,my proof is wrong without this.

I have no idea about the relationship between what you have written and the problem -- as far as I can tell you do not use the conditions of the problem anywhere. You appear to claim that in every connected non-bipartite graph, every vertex belongs to an odd cycle. But this is simply false (e.g., if there is a vertex of degree 1).