MathDB

In a simple graph

G

, an operation is defined as taking two neighbor vertices

u,v

which have a common neighbor, deleting the edge between

u,v

and adding a new vertex

w

whose neighbors are exactly the common neighbors of

u

and

v

. Starting with the complete graph

G=K_n

where

n\ge 3

is a positive integer, find the maximum number of operations that can be applied.
Proposed by Deniz Can Karaçelebi

Problem Statement