Let $e=uv$ be an edge of $G$.
Let $f$ and $g$ be the other two edges incident with $v$.
Let $G'=G-f-g$.
Claim 1: $G'-v$ is 2-connected.
$G'-v$ is the same as $G-v$.
Claim 2: $G'$ has a perfect matching.
You can prove this by showing directly that the Tutte condition holds.
I assume that you are familiar with the standard proof of Petersen's theorem,
so I will not elaborate on every detail.
Note that $G'$ has only 2 vertices of even degree.
Let $S$ be a vertex subset of $G$, $o(G'-S)$ the number of odd components of $G'-S$.
At most one odd component can contain $v$; that component can have as few as 1 edge to $S$ (since $G'$ is still connected).
All other odd components contain a vertex different from $v$, so because $G'-v$ is 2-connected all other odd components have at least 2 edges to $S$.
At most two odd components can contain a vertex of even degree (even in $G'$).
All other odd components must have at least three edges to $S$ (as in the
standard proof of the Petersen theorem).
Let $x$ be the number of edges between $S$ and the odd components of $G'-S$.
We have just shown that $x\geq 3o(G'-S)-4$.
On the other hand $S$ can accomodate at most $3|S|$ edges, so $x\leq3|S|$.
This means that $o(G'-S)\leq|S|+\frac{4}{3}$.
Now finally use the fact that $G$ is even, so $o(G'-S)$ and $|S|$ have the same parity.
This shows that $o(G'-S)\leq|S|$ and the Tutte condition holds.
Final argument: the perfect matching of $G'$ is a perfect matching of $G$ and it contains $e$,
since the degree of $v$ in $G'$ is 1.
Hint:
- Let $M$ be some perfect matching n $G = (U,V,E)$.
- Denote by $\vec{G}$ the graph $G$ directed by $M$, that is, $$
\vec{E} = \{(u,v) \mid \{u,v\} \in E \cap M\} \cup \{(v,u) \mid \{u,v\} \in E \setminus M\}.$$
- Set $C_1, C_2, \ldots$ to be the strongly connected components of $\vec{G}$.
- These components have very special structure, in particular any edge that is contained within any oh those components belongs to some perfect matching.
Different hint:
(This is actually the very same solution, only the formulation is a bit simpler, however, not as nice.)
- Let $M$ be some perfect matching.
- Take any vertex $v \in V$. Set $v_0 = v$. Assume it has an edge $\{v_0,u_0\}$ that does not belong to any perfect matching (otherwise you are done), where $u_0$ is the other vertex incident to that edge.
- Let $v_1$ be a neighbor of $u_0$ in $M$.
- Repeat these steps to get a sequence $v_0,u_0,v_1,u_1,v_2,\ldots$ alternating between $V$ and $U$, and also edges between them alternating between $E \setminus M$ and $M$.
- Because the graph is finite, you will find $v_i = v_j$ (or $u_i = u_j$) for some $i < j$, and let $i$ and $j$ be the first such pair.
- Observe that you got an alternating cycle.
I hope this helps $\ddot\smile$
Best Answer
The problem you're asking about is Exercise 3.3.16 on p. 147 of the second edition of West's Introduction to Graph Theory. The "even order" assumption is of course redundant when $k$ is odd. The proposition is trivial if $k=1$ ($G=K_2$) or $k=2$ ($G$ is an even cycle). The case $k=3$ does not seem trivial. Leafing through the preceding pages of text, I found the case $k=3$ stated and proved as Corollary 3.3.8 on p. 139. If I had to work this exercise, the first thing I'd do is study that proof carefully. Then I try to generalize it, first for $k=4$, then for general $k$. Also, hoping it's not too much of a spoiler, I might look for a hint in Appendix C: Hints for Selected Exercises. The hint for this one is on p. 511, and it just says "Generalize the argument of Corollary 3.3.8."
But maybe you've already read that hint, and you need help in figuring out how to generalize the proof of 3.3.8? In that's where you're stuck, you should have said so.