17 апреля снова приступили к разрушению карсских укреплений. Однако здесь пришлось столкнуться еще с одной трудностью. Жители с большой неохотой выполняли требования русского начальства, да и то под большим нажимом. Помимо этого, они отправили турецкому правительству жалобу на это распоряжение. В связи с этим генерал Хрулев обратился с просьбой работы по разрушению укреплений прекратить и оставить их в том виде, в каком они находились. Он также сообщал, что для взрыва цитадели направил инженера полковника Пашканга. Поскольку генерал Бебутов данного вопроса без наместника решить не мог, то, не давая приказа о прекращении работ, 27 апреля обратился к Муравьеву, находившемуся на Кавказской линии, испрашивая согласия прекратить разрушение укреплений и не назначать жителей на эти работы.
К этому времени, согласно заключенному миру, многое уже было ясно. Россия возвращала Турции Южную Бессарабию. Российское правительство также обязано было возвратить Турции крепость Карс и область. Поэтому правительство сочло за лучшее не уничтожать укрепления Карса, чтобы Россию не обвинили в нарушении договора.
Повеление о прекращении работ по срытию укреплений в Карсе было получено 4 мая. Но к этому времени, пользуясь установившейся погодой, многое было сделано: срыты все верки, ранее занимавшиеся турецкими войсками над господствовавшими над городом высотами, пороховые погреба и блокгаузы разрушены. Кроме того, было срыто большое укрепление, известное как кладбищенское на левом берегу реки Карс-чая. В цитадели, состоявшей из трех ярусов, верхний ярус, представлявший башню на 8—10 орудий, был обрушен взрывами. Второй ярус представлял собой стену с амбразурами и башню на 4 орудия. В нижнем ярусе три пороховых погреба были взорваны, а в трех разобраны крыши.
После заключения Парижского мира нужно было решить много вопросов в Закавказье, связанных с возвращением территорий Турции, а также присоединенных к России территориий и занятия русскими войсками Сухума и Редут-Кале. Князь Бебутов, докладывая генералу Муравьеву о положении дел, писал относительно Абхазии: «Полагал бы я необходимым сперва определить положение правителя Абхазии кн. Ширвашидзе, к нашему правительству». Что касается Редут-Кале, предлагал расположить две роты не только в нем, но и в бывшем укреплении Николаевском.
После завершения Крымской войны Н.Н. Муравьев твердо решил уйти в отставку и подал прошение на имя императора, не дожидаясь коронации, которое было удовлетворено. 22 июля 1856 г. высочайшим приказом он был освобожден от должностей главнокомандующего корпусом и наместника. Главнокомандующим Кавказским корпусом и наместником был назначен генерал-адъютант князь А.И. Барятинский. Такое назначение вполне устраивало князя Бебутова, у которого с Барятинским были не только хорошие отношения, но тот его знал и очень высоко ценил.
Н.Н. Муравьев не стал ждать приезда своего преемника в Тифлисе. Ему с Барятинским не хотелось встречаться, и он покинул Кавказ до его приезда. Отъезжая с Кавказа, Н.Н. Муравьев отдал свой последний приказ о возложении обязанностей командующего корпусом на генерала В.И. Бебутова. В соответствии с ним генерал-лейтенант Бебутов 19 августа отдал приказ по Отдельному Кавказскому корпусу, который был опубликован в газете «Кавказ»: «В исполнение Высочайшего повеления, объявленного г. генерал-адъютантом, генералом от инфантерии Муравьевым 1-м, в приказе по отдельному Кавказскому Корпусу, от сего числа № 476, вступаю я теперь же во временное командование войсками сего Корпуса, впредь до прибытия на Кавказ генерал-адъютанта Князя Барятинского. Объявляя о том по Отдельному Кавказскому Корпусу, предписываю с донесениями и представлениями входить установленным порядком ко мне по команде. Подлинный подписал: Временно командующий Отдельным Кавказским Корпусом, генерал-лейтенант Князь
Василий Иосифович очень тепло простился с Н.Н. Муравьевым.
Следует отметить, что в это время В.И. Бебутов все чаще прибаливал. Но он не придавал этому особого значения, считая, что это старческие симптомы. Как-никак, уже 65 лет. Сказывались военные походы, нервные перегрузки. Он подумывал об отставке. Да все дела не отпускали. Вот и теперь время бы уйти в отставку, но снова произошла смена наместника и главнокомандующего. Василий Иосифович решил дождаться приезда князя Барятинского и потом уже решать, как быть дальше.
Генерал Барятинский после коронации в Москве императора Александра II вскоре выехал на Кавказ. Он решил не трястись по дальней дороге, а плыть по Волге, а затем до форта Петровского на Каспии, куда он и прибыл. Генерал Бебутов получал с его пути эстафеты с сообщениями, где он находится, отдельные указания.