劉邦在成皋養好了箭傷，回到關中櫟陽安撫百姓，四日后返回廣武軍中。劉邦到櫟陽的目的顯然不只是安撫百姓，而是通過這個行為給自己做征兵廣告，漢軍兵源再次得以補充。
龍且被殺、田廣被俘，韓信破齊對項羽的打擊非常大，這意味著他的大后方出現了問題。同時，彭越又在梁地經常截斷楚軍糧道，導致楚軍雖在廣武圍困漢軍，但后方失守、糧道不穩，并非長久之計。而劉邦雖然被圍，但得益于蕭何在巴蜀的苦心經營，兵源和糧餉得以不斷補充，戰略上實則并不處于劣勢。此時劉邦心里還有一份牽掛，就是被項羽擄走作為人質的劉太公和呂雉。
項羽損將斷糧，又被韓信大兵壓境，在這樣的局勢下，劉邦看到了機會。于是派陸賈前去說服項羽，希望能迎回家人，但未能成功。隨后又令侯公，也就是姓侯的一位辯士，再次前往楚軍游說項羽，這次不但成功使呂公、呂雉被釋放，還與項羽達成協議，以鴻溝為界中分天下，鴻溝以西為漢，鴻溝以東歸楚。
項羽以劉邦家人為人質，是極大的政治資本，絕不可能輕易歸還，甚至連名士陸賈都無法說服項羽。就是這么一件難于登天的事兒，卻被名不見經傳的侯公辦成了，可想而知，這是一番多么精彩的辯詞。但遺憾的是，《漢書》《史記》都沒記錄候公到底說了什么，給后人留下了很大的想象空間。
一千年后，北宋著名詞人蘇軾寫了一篇《代侯公說項羽辭》，描述了侯公說服項羽的經過。
大概意思就是劉邦志在天下，不會因親人死活而改變，項羽雖然首先舉起反秦大旗，但數年征戰下來犯了不少錯誤，導致如今楚的優勢喪失殆盡，如果還不肯歸還呂公、呂雉，則會加重漢軍的仇恨，為劉邦再增加一條滅楚的理由，不如就此罷兵，共分天下。當朝史官都未記載的細節，被蘇軾在一千年后描繪的有聲有色，可信度應該不高，權當做后人的一種猜想吧。
蘇軾對細節的描寫可能只是一種合理的猜測，但對大局勢的分析是很值得參考的。巨鹿之戰使項羽的名望和實力都到達了頂峰，諸侯無不臣服。可是他目光短淺、用人失當，楚漢實力對比在短短幾年內發生了反轉。
雖然現在兩軍在廣武都是人困馬乏，無力再戰，但劉邦手握巴蜀、關中大后方，占據敖倉，韓信一路平定了代、趙、燕、齊，彭越不斷的騷擾楚軍補給線。如果繼續相持下去，漢軍的優勢會越來越明顯。此時是通過和平手段接回呂公、呂雉的最佳時機，如果項羽還是不肯，等劉邦實力恢復起來，必然會遭到更激烈的報復。以劉邦之堅決果敢和心狠手辣，是不可能因為兩個親人而放棄天下的。
九月，項羽如約放歸了太公和呂雉，漢軍將士大呼萬歲。侯公因此立下大功，被封為平國君。
鴻溝之約達成后，項羽罷兵東歸，劉邦也準備回到關中。這時，張良、陳平勸諫道：“如今漢已擁有天下之大半，諸侯也都依附于我們，而楚軍此時人困馬乏、缺少糧草，若不趁機消滅他們，就是養虎為患。”劉邦采納了他們的建議。
這就是所謂兵不厭詐，為了爭奪天下，可以撕毀已經達成的約定，盡管這非常不上臺面，但終究是幫助劉邦取得了天下。因為誰也不敢說，放項羽東歸之后，他又會在哪一天又卷土重來。正如杜牧的詩句，江東子弟多才俊，卷土重來未可知。
漢五年十月，劉邦帶兵追擊項羽到陽夏南，準備與齊王韓信、魏國國相彭越的軍隊會師后，共同攻擊楚軍。但一直走到了固陵，還沒遇到這兩路大軍。楚軍趁機大敗漢軍，劉邦撤退，堅壁不出。
劉邦對此感到很郁悶，就問張良：“這些諸侯都不聽話，可咋辦呢？”這是劉邦的特點，遇到難題就問手下，這咋辦，那咋辦。好在劉邦帳下謀士如云，他自己也善于聽取建議。
張良說：“我們已經基本擊敗了楚軍，但還未對這些功臣進行分封，所以他們不來也覺得理所應當。如果大王能與功臣們共分天下，他們自然就會聽話。立韓信為齊王并非大王本意，韓信他自己也非常清楚；而彭越攻下梁地，因為這里最初封給了魏豹，他只能做個相國，如今魏豹已死，大王卻未能盡早封他為王。建議大王最好把睢陽以北至谷城的地盤封給彭越，把陳以東至海邊的地盤封給韓信，韓信的家在楚地，也正合他的本意。如此，兩人就都為自己而戰，擊敗楚軍就很容易了。”劉邦聽從了陳平的建議，派使者前往韓信、彭越軍中傳達封王的命令。得到了劉邦的分封，兩人果然都帶著兵馬前來相助。
十一月，劉邦派堂兄弟劉賈南渡淮水進入楚地，圍困壽春。同時，漢軍還派人前往楚軍，成功的策反了大司馬周殷。周殷叛變原因至今未出現在任何史書記載中。陳平曾點名指出項羽的四大“骨鯁之臣”：亞父范增、鐘離眛、龍且以及周殷。由此可見，周殷官至楚軍大司馬，絕不是個小人物，說服周殷反叛肯定不是容易的事。
但周殷的叛變似乎非常干脆，因為他馬上就用舒縣的兵屠了六縣，還率領九江郡的楚兵配合英布屠了城父（fǔ），并隨劉賈與劉邦會師。這引起了后世的無限猜想，是不是項羽曾經嚴重的得罪過周殷，才導致他一有機會就頭也不回的叛離了楚。
歷史的真相我們已不得而知，但非常清楚的是，周殷的叛變對項羽是致命的。因為楚國的首都彭城北有韓信，西有彭越，兩人均接受了劉邦的分封，如今南部地區因周殷叛變也歸了漢軍，楚軍被壓縮在很小的一塊區域內，形勢岌岌可危。
項羽背約被劉邦指責為“項羽十罪“之首，還曾以此號召諸侯共同反楚，而如今自己卻故技重施。這背后依然是實力的保障，弱者才用盟約自保，而強者只靠實力說話。
所以，哪有什么絕對意義的正義之師，不過是斗爭者彼此的攻訐手段罷了。