Para cada n≥2n≥2n \geq 2 existe un grafo simple de n-vértices cuyos vértices tienen grados distintos

Question

Para cada n≥2n≥2n \geq 2 existe un grafo simple de n-vértices cuyos vértices tienen grados distintos

Matemáticas
Teoría de grafos
combinatoria
Matemáticas discretas

Cero

Así que me dieron esta pregunta. Para cada $n \geq 2$ existe un grafo simple de n-vértices cuyos vértices tienen grados distintos. He visto preguntas algo similares como Dado un gráfico simple con $n = 4k + 2$ vértices. ¿Pueden los vértices de este gráfico tener grados distintos? ¿El estilo de solución es el mismo? Estoy confundido acerca de esta pregunta.

mateo samuel

Si

n = 2

$n=2$ esto no es cierto ¿Era una pregunta de prueba o refutación?

Brian M Scott

¿Estás seguro de que no te pidieron probar eso para

n \geq 2

$n\ge 2$ no existe un

n

$n$ -gráfico simple de vértices cuyos vértices tienen grados distintos? Porque esa afirmación es cierta y NS ha dado algunos consejos útiles para probarla.

Respuestas (1)

Para cada n≥2n≥2n \geq 2 existe un grafo simple de n-vértices cuyos vértices tienen grados distintos

Si $n=2$ esto no es cierto ¿Era una pregunta de prueba o refutación?
¿Estás seguro de que no te pidieron probar eso para $n\ge 2$ no existe un $n$ -gráfico simple de vértices cuyos vértices tienen grados distintos? Porque esa afirmación es cierta y NS ha dado algunos consejos útiles para probarla.

NS · Answer 1

Sugerencia ¿ Cuáles pueden ser los grados de los vértices en un gráfico simple con $n$ vértices?

Pista 2 ¿Qué significa si todos son diferentes?

Pista 3 ¿Qué significa el grado mayor? ¿Qué pasa con los más pequeños?

Para cada n≥2n≥2n \geq 2 existe un grafo simple de n-vértices cuyos vértices tienen grados distintos

Cero

mateo samuel

Brian M Scott

Respuestas (1)

NS

Un gráfico máximo conectado GGG sin ciclos de longitud de al menos k+1k+1k+1 tiene |V(G)|≤k|V(G)|≤k|V(G)| \leq k o tiene un vértice cortado cuando k≥2k≥2k \geq 2

Problema sobre la existencia de un ciclo de Bruijn.

Pregunta sobre una prueba de "El gráfico GGG no tiene ciclos impares ⟹⟹\implica que GGG es bipartito"

probar que para n≥2n≥2n \geq 2 no existe un grafo simple de n-vértices cuyos vértices tengan grados distintos

Número máximo de ciclos de expansión sin borde común en un gráfico completo

Varias pruebas relacionadas con las definiciones de árboles y bosques.

¿Por qué el problema del vendedor ambulante es "difícil"?

Definición de gráfico bipartito del libro de Murty-Bondy

Número de rutas óptimas a través de una cuadrícula con una restricción de ruta ordenada

Demuestre que el tamaño del gráfico de Turan Tr(n)Tr(n)T_r(n) es al menos (1−1r)(n2)(1−1r)(n2)(1 - \frac{1}{r} ) \binom{n}{2}.