Problema de optimización combinatoria de gráficos

Question

Dejemos que $G$ sea un gráfico simple con un conjunto de vértices $V$ , tal que para dos vértices cualesquiera $u,v\in V$ tenemos al menos $k$ trayectorias disjuntas de aristas de longitud $2$ (es decir, formado por $2$ bordes) que conectan $u$ con $v$ . Sea $n=|V|$ sea el número total de vértices de $G$ .

---

Pregunta: ¿Cuál es el valor mínimo de $k$ expresado en función de $n$ para garantizar que $G$ debe ser un gráfico completo?

Answer 1

La respuesta es $k=n-2$ . Para ver esto, primero hay que tener en cuenta que $k \geq n-2$ ya que el gráfico completo en $n$ vértices menos una arista tiene la propiedad deseada para $k=n-3$ . Para la otra desigualdad supongamos que $G$ es un $n$ -de vértices tal que para todos los distintos $u, v \in V(G)$ Hay por lo menos $n-2$ trayectorias de borde disjuntas entre $u$ y $v$ . Afirmamos que $G$ debe ser un gráfico completo. Supongamos que no. Entonces $ab \notin E(G)$ para algunos $a,b$ . Sea $c \notin \{a,b\}$ . Entonces hay como máximo $n-3$ trayectorias disjuntas de aristas de longitud $2$ entre $a$ y $c$ , lo cual es una contradicción.