En teor\u00eda de grafos una t\u00e9cnica bastante usada es proceder suponiendo que la proposici\u00f3n es falsa y analizando las consecuencias de dicha suposici\u00f3n hasta llegar a una contradicci\u00f3n.<\/p>\n
El siguiente teorema fue realizado por Erd\u00f6s en 1965.<\/p>\n
<\/p>\n
Teorema. (Erd\u00f6s)\u00a0<\/strong>Cada grafo sin lazos contiene un subgrafo bipartito generador F<\/span> tal que d_F(v)\\geq \\frac{1}{2} d_G(v)<\/span> para todo v\\in V<\/span><\/p>\n Demostraci\u00f3n.<\/p>\n Sea G<\/span> un grafo sin lazos. G tiene un subgrafo generador bipartito, uno de ellos es, por ejemplo, el subgrafo generador vac\u00edo. Sea F=F[X, Y] <\/span> un subgrafo generador bipartito con el m\u00e1ximo n\u00famero de enlaces. Afirmamos que F <\/span> satisface la propiedad requerida. Supongamos que no, entonces existe alg\u00fan v\u00e9rtice tal que<\/p>\n <\/p>\n d_F(v) < \\frac{1}{2} d_G(v)<\/span><\/p>\n Sin p\u00e9rdida de generalidad, podemos suponer que v est\u00e1 en el conjunto X. Consideremos el subgrafo bipartito generador F' cuyo conjunto de enlaces consiste de todos los enlaces de G con un terminal en X\\setminus v <\/span> y otro en\u00a0 Y\\setminus v <\/span>. El conjunto de enlaces de F' es el mismo conjunto de enlaces de F excepto por aquellos enlaces incidentes en v, aquellos que est\u00e1n en F no est\u00e1n en F' y aquellos que no est\u00e1n en F est\u00e1n en F'.<\/p>\n \\begin{aligned}e(F')=e(F)-d_F(v)+(d_G(v)-d_F(v))\\\\=e(F)+(d_G(v)-2d_F(v))>e(F) \\end{aligned} <\/span>\n Pero esto contradice que F sea el subgrafo bipartito generador con mayor n\u00famero de enlaces.<\/p>\n","protected":false},"excerpt":{"rendered":" En teor\u00eda de grafos una t\u00e9cnica bastante usada es proceder suponiendo que la proposici\u00f3n es falsa y analizando las consecuencias de dicha suposici\u00f3n hasta llegar a una contradicci\u00f3n. El siguiente teorema fue realizado por Erd\u00f6s en 1965. Teorema. (Erd\u00f6s)\u00a0Cada grafo sin lazos contiene un subgrafo bipartito generador tal que para todo Demostraci\u00f3n. Sea un … Sigue leyendo Una prueba por contradicci\u00f3n<\/span><\/a><\/p>\n","protected":false},"author":5810,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1419472],"tags":[],"class_list":["post-294","post","type-post","status-publish","format-standard","hentry","category-teoria-de-grafos"],"_links":{"self":[{"href":"https:\/\/blog.espol.edu.ec\/adguale\/wp-json\/wp\/v2\/posts\/294","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/blog.espol.edu.ec\/adguale\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blog.espol.edu.ec\/adguale\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blog.espol.edu.ec\/adguale\/wp-json\/wp\/v2\/users\/5810"}],"replies":[{"embeddable":true,"href":"https:\/\/blog.espol.edu.ec\/adguale\/wp-json\/wp\/v2\/comments?post=294"}],"version-history":[{"count":7,"href":"https:\/\/blog.espol.edu.ec\/adguale\/wp-json\/wp\/v2\/posts\/294\/revisions"}],"predecessor-version":[{"id":301,"href":"https:\/\/blog.espol.edu.ec\/adguale\/wp-json\/wp\/v2\/posts\/294\/revisions\/301"}],"wp:attachment":[{"href":"https:\/\/blog.espol.edu.ec\/adguale\/wp-json\/wp\/v2\/media?parent=294"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blog.espol.edu.ec\/adguale\/wp-json\/wp\/v2\/categories?post=294"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blog.espol.edu.ec\/adguale\/wp-json\/wp\/v2\/tags?post=294"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}