Olimpiada China Team Selection Test 2014 Problema 11

Encuentre la constante positiva más pequeña $c$ que satisface: Para cualquier grafo simple $G=G(V,E)$ , si $|E|\geq c|V|$ , entonces $G$ contiene $2$ ciclos sin vértice común, y uno de ellos contiene una cuerda. Nota: El ciclo del grafo $G(V,E)$ es un conjunto de vértices distintos ${v_1,v_2...,v_n}\subseteq V$ , $v_iv_{i+1}\in E$ para todo $1\leq i\leq n$ $(n\geq 3, v_{n+1}=v_1)$ ; un ciclo que contiene una cuerda es el ciclo ${v_1,v_2...,v_n}$ , tal que existe $i,j, 1< i-j< n-1$ , que satisface $v_iv_j\in E$ .

27

0

Kevin (AI)

Inicia sesión para agregar soluciones y pistas

Problemas Recomendados