В ходе переговоров в Париже о заключении мира между Россией и державами, с которыми она воевала, предполагалось, что Россия передаст Турции Карс в обмен на Севастополь. Генерал Муравьев, находившийся на Северном Кавказе, 15 марта направил письмо князю Бебутову, в котором писал о том, что его брат Михаил, обеспокоенный делами на Кавказе, сообщал, что близится подписание в Париже мира и предполагается отдать Турции Карс. По этому поводу Михаил спрашивал у брата: «Неужели ты не уничтожишь, по крайней мере, Карсских укреплений, как они взорвали наши Севастопольские». Муравьев писал, что он лично поручил командующему корпусом генералу Хрулеву срыть Карсский укрепленный лагерь, начальнику штаба корпуса генералу Индрениусу указал, что именно уничтожить, а что оставить. Поэтому командующий просил князя Бебутова подтвердить это распоряжение письменно, с тем «чтобы приступить к сему делу при первой возможности, т. е. при стаянии снегов, начав срытие с предназначенных к уничтожению».
После взятия Карса генерал Муравьев, уведомляя военного министра Долгорукова о Карсских укреплениях, предложил их уничтожить и срыть. Император Александр II поддержал предложение, учитывая, что близилось завершение войны и России, возможно, предстояло возвратить Карс туркам. 14 марта военный министр сообщил Н.Н. Муравьеву, что император дал указание, чтобы «уничтожение Карсских укреплений приведено было в исполнение в возможно скорейшее время». Поэтому министр просил ускорить работы. Одновременно он потребовал немедленно представить ему сведения о том, что уже сделано по срытию укреплений.
Н.Н. Муравьев поручил генералу Бебутову ускорить работы по уничтожению крепостных укреплений, сделав на этот счет соответствующие распоряжения. Князь Бебутов, в свою очередь, поручая это сделать командующему действующим корпусом генералу Хрулеву и исходя из огромного объема работ, предписал использовать для ускорения уничтожения крепостных сооружений не только солдат, но и жителей города. Одновременно он потребовал ускорить вывоз из Карса казенного и артиллерийского имущества, захваченного в Карсе в качестве трофеев.
Насколько своевременны были эти действия, показало сообщение 22 марта генералу Муравьеву от военного министра о том, что мир в Париже подписан и согласно ему Турции должна быть возвращена Карсская область: «Предвидя наступившую ныне необходимость эту, я уже просил вас сообщить мне, в каком виде Карсская крепость находится в настоящую минуту, взорваны ли, хотя отчасти, построенные Англичанами и Турками верки и повреждены ли они, по крайней мере, весенним разливом вод. Ответа вашего я ожидаю с нетерпением, ибо в. выспр. изволите согласиться, что в виду Севастополя, совершенно разрушенного, было бы прискорбно уступить неприятелю завоеванные у него укрепления в неприкосновенной целости».
Таким образом, из этого видно, что руководство России было заинтересовано в том, чтобы Карсская крепость была возвращена с наибольшими разрушениями. Этого хотели и войска на Кавказе. Поэтому Н.Н. Муравьев снова дал указание князю Бебутову всемерно ускорить работы, пока не опубликован текст договора, направляя на их производство усиленные наряды населения и все наличные силы военных.
В свою очередь, турки, обеспокоенные тем, что в крепости Карс идут работы по демонтажу укреплений, направили к русскому командованию на Кавказе своего представителя для выяснения вопросов в связи с этим.
12 марта 1856 г. в Тифлис прибыл посланец Селим-паши мирливу Сеид-Хамди-паша для того, чтобы уточнить вопросы, связанные с определением, где будут находиться после заключения перемирия русские и турецкие посты. Поскольку Муравьев в это время выехал на Кавказскую линию, то принимал его генерал Бебутов, который не стал глубоко вдаваться с ним в переговоры. Используя свою обаятельность, он обласкал турецкого посланца Сеид-Хамди, устроив пышный прием, значительно усыпив его бдительность, и сделал более покладистым. В ходе проведенных переговоров они договорились по всем вопросам. После этого князь Бебутов отправил его 17 марта в Эрзерум с приветливым посланием для Селим-паши, в котором сообщал о посланных с такими же полномочиями русских офицерах. Таким образом, генерал Бебутов сделал все для того, чтобы затянуть переговоры.
А работы по уничтожению крепости Карс шли крайне медленно. Начальник Карсской области полковник Лорис-Меликов 8 апреля доносил командующему действующим корпусом, что хотя и приступили к срытию верков и других укреплений в крепости, но сделать это быстро невозможно, так как во рвах лежали глыбы льда, а оттаявшая земля пропитана водой настолько, что невозможно работать. Но, исходя из требования военного министра о том, что в виду разрушения Севастополя «было бы прискорбно уступать неприятелю завоеванные у него укрепления в неприкосновенной целостности», генерал Бебутов дал указание генералу Хрулеву, невзирая ни на что, немедленно приступить к работам.