Edit. The OP said they would like to have a former extended comment of mine concerning (some version of) a 'vertex-splitting-operation', which were deleted because of their being only tenuously related to what the OP is actually asking for, and because the heuristic illustrations I gave were not good enough to leave them visible.
So I here give a new version of these comments, this time, with even more warnings that this does not get any closer to where the OP seems to be wanting to go, and this time with decent illustrations.
For brevity:
'graph'$:=$'irreflexive symmetric binary relations on a set'
'1-factor'$:=$'perfect matching'
$\mathsf{1Factors}(G)$ $=$ set of all 1-factors of $G$
'circuit'$:=$'2-regular subgraph'
at times, simple quotation marks are used to convey reservation towards using some word for concepts which do not seem to deserve to be called thus.
It should be pointed out up front that the following
- is relevant to the OP in so far as this 'operation' is the only noteworthy 'operation' (known to me) on the class of all graphs which exactly preserves the total number of 1-factors
is irrelevant in so far as it does not get the OP any closer to a bipartite graph, and in a rather strong sense of 'not any closer': the 'operation' preserves the cycle spectrum of the 'transformed' graph; stronger still, it even preserves the cycle frequency, and stronger still, in a precise sense, the 'circuits are not changed at all':
while the 'operation' involves arbitrary choices($\approx$is not canonical$\approx$can never become a reasonable functor since any reasonable category on the relevant class 'should' have enough morphisms to 'snitch on' the operation's non-canonicity), we have the following:
There is a canonical bijection between the set of all circuits in the relevant graph $G$, and the set of all circuits in $\mathrm{AnySequenceOfTheVathingOperation}(G)$.
Description of the 'operation' in question.
There is the following informally-defined vertex-splitting-like operation, which is relevant to, yet apparently rather insufficient for, solving the OP's problem.
In the literature, the operation is sometimes attributed to D.B.Wilson.
Since it is so different from another, more usual, notion of 'vertex splitting' (which is just what you think it is), I propose to call this vertex-splitting-like operation
This is partly a contraction of an (also, unattested) term '$v$-pathing', and partly a visual pun, reminding one that this operation replaces a $\underline{\text{v}}$ertex by a 3-vertex-path (which is often drawn like the letter v).
In order not to unduly slight the vathing operation, one should point out right away that:
vathing is useful in another context, notably for practical 1-factor-counting-algorithms, and for complexity-theorems, in particular because vathing gives a systematic way to reduce to the context of graphs with maximum degree $\leq 3$
Edit: (I add some not very polishes, not very well thought-out considerations on what I mean by my saying vathing is not well-defined.)
However, I think it should be emphasized that:
no one has ever defined this vertex-splitting-like operation as a class function from the class of all finite graphs to itself,
it won't be defined as such a function here either,
this is one (there are many similar other example) easy example that 'class function' at times really means something: it is trivial to 'commit' to a specified, possibly rather large infinite set $S$, then only consider graphs with vertex set equal to this set, then exploit the set-theoretic specifics of $S$ to define vathing as a set-map $\mathsf{GraphsOn}S\to\mathsf{GraphsOn}S$ (I won't give an explicit example here, since any explicit example seems so arbitrary; you can do something like taking a set with a total order and then 'split' according to some 'rule' exploiting the order). Yet it seems impossible (to me) to define vathing as a function on the proper class of all finite graphs. And this fails because of size alone, we need not even speak about structural considerations like making vathing compatible with morphisms between graphs. A somewhat equivalent point of view: it seems impossible to define vathing as a set-map which takes the complete theory of the given graph to the complete theory of the resulting graph (with 'complete theory' w.r.t. some specified countable set of variables and w.r.t. the usual first-order logic of graphs), while this is possible for e.g. the usual example of a nontrivial class-function on the class of all finite graphs: barycentric subdivision. Barycentric subdivision can be described as a set-map between the complete theories characterizing the graphs up to isomorphism.
[Technical remark: the above applies to any $\aleph_0$-categorical graph. Every finite graph is $\aleph_0$-categorical. Some infinite graphs are $\aleph_0$-categorical too. Perhaps it would be an interesting challenge to prove or disprove the following claim: let $\mathcal{L}=\{\sim,\vee,\wedge,\Rightarrow,(,)\}\cup\{x_i\colon i\in\omega\}$, where the elements of the set are (names for) explicitly specified mutually distinct sets, and where yes of course the logical symbols could be pared down a bit yet this is inessential, the usual language of the first-order logic of graphs. Let $\mathcal{F}$ denote the set of all well-formed formulae over $\mathcal{L}$. For each graph $G$ with vertices from $\omega$ let $\mathrm{Th}_{\mathcal{F}}(G)$ denote the set of all elements of $\mathcal{F}$ which are true for $G$ w.r.t. the usual semantics. Claim: there does not exist any set-map $f\colon\mathcal{F}\rightarrow\mathcal{F}$ such that for each finite graph $G$ the directed image $\mathcal{T} := f``\mathrm{Th}_{\mathcal{F}}(G)$ of the complete theory of $G$ under $f$ has the property that $\mathcal{M}:=\mathrm{Mod}_{\mathsf{GraphsWithVertexSet}\omega}(\mathcal{T})$ has the following properties:
all elements of $\mathcal{M}$ are isomorphic graphs, all isomorphic to some finite graph $H$ with vertices from $\omega$,
$H$ has maximum degree at most $3$,
$H$ can be obtained from $G$ by finitely many vathing 'operation'.
This then would define vathing as a class function. It seems quite clear that there is nothing to 'categorically guide' the arbitray choices one has to make in the vathing steps, though I don't have time to think about this now.
End of edit.
(That is, no one seems to have ever defined it as a class-function
$\mathsf{UndirectedGraphs}\rightarrow\mathsf{UndirectedGraphs}$.
It is usually informally described in meta-language,
insinuating that relevant arbitrary choices can be made.
This is not a definition.
Not to speak of defining vathing as an endofunctor of $\mathsf{UndirectedGraphs}$
for reasonable non-discrete categories on $\mathsf{UndirectedGraphs}$.)
It seems to me that currently the ontological status of
'vathing' is no better than something linke
'class-function $\mathsf{UndirectedGraphs}\rightarrow\mathsf{SetsOfUndirectedGraphs}$',
the latter function being obtained by making all the suitable choice at once.
It is not clear whether one even can do any better than that,
i.e., whether there is any intrinsic property which could be
utilized to define 'vathing' as a function.
Currently vathing is reminiscent of the transition-function
of a non-deterministic Turing machine.
Informal 'definition' of vathing a vertex.
Let $G=(V,E)$ be a graph and $v\in V$ an arbitrary vertex.
- 'Choose' a non-empty subset $S$ of the neighbor set $N_G(v)\subset V$.
- 'Remove' the set $\{ \{u,v\}\colon u\in V, \{u,v\}\in E \}$ from $E$ to obtain a set $E'$.
- 'Create'/'name' three distinct sets $v',v'',v'''$ distinct from all other sets in the previous context.
- 'Add' the set $\{\{u,v'\}\colon u\in S\}\cup\{\{v',v''\}\}\cup\{\{v'',v'''\}\}\cup\{ \{v''',w\}\colon w\in V\setminus S \}$ to $E'$ to obtain a set $E''$.
- Let $v\mathrm{ath}(G):=(V\setminus\{v\}\cup\{v',v'',v'''\},E'')$.
Lemma (relevant to the OP). $\Phi(v\mathrm{ath}(G)) = \Phi(G)$, for any simple undirected graph $G$, any $v\in V(G)$, and any 'performance' of the vathing operation by going through the 5 steps above, and with $\Phi(\cdot)$ denoting the cardinal number of the set of all 1-factors.
Sketch of proof of stronger version of the lemma. There is the following 'canonical'($\approx$choice-free) bijection $\mathsf{1Factors}(G)\rightarrow \mathsf{1Factors}(\text{$v$ath}(G))$: given $M$ in the domain, map each $e\in M$ which does not contain $v$ to itself (and this is in the codomain), and map the unique (unique because of definition of 1-factors) edge $uv$ to the edge $uv'$ in the codomain, and add to this $\lvert M\rvert$-element set of edges the edge $v''v''$. This is defined, and without choices. It is injective since, given perfect matching $M'$ and $M''$ of $G$, if $M'$ and $M''$ are distinct, then either they differ where the function is the identity, i.e. 'away' from $v$ so their being distinct is 'visible' in the result, too, or they agree in all edges not containing $v$, hence would have to differ in the sole edge containing $v$, hence these edges would have to have distinct 'other' vertices, which is impossible since we are speaking about perfect matchings (so the 'or' clause is impossible and the proof of injectiveness complete); it is surjective since given a perfect matching $M$ in the 'resulting' graph, you can just leave out the edge $v''v'''$ from $M$ and take the 'projection' of the remaining matching to a matching of $G$ to get a matching of $G$ which maps to $M$.
This completes the proof of the lemma.
Some illustrations.
Petersen graph. The following shows a representation of the Petersen graph. A (nonproper) 2-coloring is indicated by blue and green. Color-conflicts are indicated by lines of the relevant color. Note that after vathing, the conflicts are the same. A perfect matching is indicate in red.
Complete graph on six vertices.
The following three illustrations shows two steps (with the arbitrary choices having been 'computed' by twice throwing a coin) of vathing applied to a complete graph on six vertices. Reason for 'six': 'four' would be too small to give an example of a reduction of vertex degree, 'five' would rule out 1-factors (which the OP is concerned with), necessitating 'six'.
The 'color-coding' is the same as above.
(Note that repeated such 'operation' will result in a graph having the same number of perfect matchings, yet having maximum degree three instead of the maximum degree five of the original graph.)
There are a few substantial related questions though, yet they are rather off-thread:
to compile a list of graph-invariants which are preserved by (any performance of) vathing. (For example, it is evident that the genus is preserved. Yet it is not clear (to me) what the answer to the following is: How is the spectrum of the adjacency matrix affected? This is tangentially relevant to the OP since one can count circuits in terms of eigenvalues. That the cycle frequency is preserved is only necessary for the spectrum to be preserved. I did not look even briefly into whether the spectrum of the adjancency matrix is preserved by vathing, but I doubt it, not knowing why. I also do not know whether someone has already analyzed vathing from this perspective.)
Most importantly, and this would be relevant to the OP:
Is there any 'good' class function $\mathsf{Graphs}\to\mathsf{Graphs}$ which (0) preserves the number of 1-factors, (1) decreases the number of odd circuits?
Of course, some such class function exists: given any graph $G$, if $G$ is bipartite, return $G$; otherwise $G$ has an odd circuit; now use the construction in this thread to just produce a bipartite graph having precisely as many perfect matchings as $G$. The number of odd circuits has strictly dropped to $0$. This class function is even 'canonical': no choice is involved, since the construction is prescribed from the outset. Yet this is not a 'good' such class function, on several counts: it takes too many steps, thus violating the OP's time constraint; moreover, the resulting bipartite graph in general bears no resemblance to the input graph. This is not a solution in any reasonable sense.
End of edit.
Beginning of old version of this answer.
The following is not an answer, yet a relevant comment that the comment box is too small to contain. This comment illustrates how important the condition of being able to do the 'conversion' in time $O(n^{c'})$ is for this problem to have substance. It also shows what the OP (presumably) means by their comment "we need a construction in polynomial time or else it is trivial." given under the OP: the following would be an answer were it not for the requirement that that conversion be calculated in polynomially many steps. Since the construction of the graph in the proof of the following lemma takes time $O(\text{number $\Phi(G)$ of perfect matchings in the given $n$-vertex graph $G$})$, and since $\Phi(G)$ can of course be exponential in $n$, the following is not a solution, since it simply takes too long.
Lemma. For each $a\in\mathbb{N}$ there exists a finite balanced bipartite undirected simple graph having exactly $a$ perfect matchings.
Proof. Let $G(a)$ denote the graph with vertex set $\{ (0,i)\colon i\in a\}\cup\{(1,i)\colon i\in a\}$ and edge set $\{ \{(0,i),(1,i)\}\colon i\in a \} \cup \{ \{(0,0),(1,i)\}\colon 1\leq i\in a \}$.
(In particular for $a=1$, the second set in the latter union is empty.)
Then the number of perfect matchings of $G(a)$ is precisely $a$, because $(0,0)$ must be matched, can be matched to precisely any one of the neighbors $(1,i)$ with $i\in a$, and, for each $i\in a$, if $(0,0)$ is assigned $(1,i)$ as its partner, then the vertex $(0,i)$ knows only one eligible vertex any more, hence must be matched to this one, and then all other matching edges are determined (and it does work out to a perfect matching). This completes the proof of the lemma.
To repeat, if the OP had not made a time constraint, then this would answer 1. affirmatively, in particular since the OP do not require any structural resemblance between the original graph and the converted graph. However, constructing $G(a)$ on a machine will take time $O(a)$, which will usually be too much.
