0
$\begingroup$

This has been put in math.SE for a while without any responses.

Given $G$ and an $f:V(G)\to{\Bbb N}$, there exists a graph $G_f$ such that $G$ is $f$-soluble if and only if $G_f$ has a $1$-factor.

"G is $f$-soluble" is defined as a graph such that there exists $w:E(G)\to{\Bbb N}$ such that $$ \sum_{uv\in E(G)}w(uv)=f(v) $$ for every $v\in V(G)$.

I believe this is a result from Tutte and it might be related to the $f$-factor theorem. But I don't remember the whole proof. One key step I remember is defining $$ V(G_f):=\{v_1,v_2,\cdots,v_{f(v)}|v\in V(G)\}. $$ Could anyone come up with a proof?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

Yes, this is a theorem that Tutte used to derive the f-factor theorem from the 1-factor theorem. He had already proved the f-factor theorem directly in 1952, in "The factors of graphs", MR0048775. The result you quote is from his paper from two years later, "A short proof of the factor theorem for finite graphs", MR0063008.

If you have trouble locating the reference, I can update this answer to give the actual argument, and construction of what you call $G_f$.

Improve this answer
$\endgroup$
0

You must log in to answer this question.