Наибольшее количество рёбер в графе, ограниченных условием...

математика комбинаторика дискретная математика граф теория графов

Добрый день! Подскажите, пожалуйста, с решением такой задачки:
"Найти наибольшее возможное количество ребер в графе с n вершинами, если известно, что среди произвольных трех его вершин есть две, не соединенные ребром."
Пробовал строить и выявлять общую формулу, но не получается. Возможно нужно использовать выборки...
Заранее спасибо за помощь!
Ответы:
Если среди 3х вершин нет 2х не соединенных ребром, то в графе есть цикл из этих трех вершин. Отсюда следует, что у нас нет циклов в графе --- а значит наш граф дерево, и количество его ребер n - 1
Первый мой ответ "с наскока" неверен. Теперь более конструктивно:


13 лет назад

RPI.su - самая большая русскоязычная база вопросов и ответов. Наш проект был реализован как продолжение популярного сервиса otvety.google.ru, который был закрыт и удален 30 апреля 2015 года. Мы решили воскресить полезный сервис Ответы Гугл, чтобы любой человек смог публично узнать ответ на свой вопрос у интернет сообщества.

Все вопросы, добавленные на сайт ответов Google, мы скопировали и сохранили здесь. Имена старых пользователей также отображены в том виде, в котором они существовали ранее. Только нужно заново пройти регистрацию, чтобы иметь возможность задавать вопросы, или отвечать другим.

Чтобы связаться с нами по любому вопросу О САЙТЕ (реклама, сотрудничество, отзыв о сервисе), пишите на почту [email protected]. Только все общие вопросы размещайте на сайте, на них ответ по почте не предоставляется.