Opa, descobri outro dia que a prova desse problema (na versão para grafos), é um teorema com nome - teorema de Dirac (não o Paul). Não deve sair por indução mesmo!
2011/2/28 Rogerio Ponce <abrlw...@gmail.com> > Oi Bernardo e Pedro, > voces tem razao! > Nao da' para usar inducao quando temos 2K pessoas, pois ao tirarmos o Joao, > talvez nem todos os participantes do grupo 2K-1 permanecam com o minimo de K > amigos ( teto(2K-1) = K ). > Portanto, nao podemos aplicar a hipotese ao grupo 2K-1. > Em provas por inducao, qualquer falta de atencao induz ao erro... > :) > Abracao, > Rogerio Ponce > > > Em 25 de fevereiro de 2011 13:48, Bernardo Freitas Paulo da Costa < > bernardo...@gmail.com> escreveu: > > Oi Ponce ! >> >> 2011/2/25 Rogerio Ponce <abrlw...@gmail.com>: >> > Bernardo, >> > acho que voce se confundiu nisso daqui: >> > >> > "Se você retirar qualquer um dos participantes de grupo, já era, porque >> > sobram (sem perda de generalidade) A,B e C, e você não pode botar A do >> lado >> > de C..." >> > >> > Nos queremos justamente colocar pessoas lado a lado, e o grupo esta' >> reunido >> > numa roda. >> Ah, ok... Mas eu continuo achando que "botar as pessoas lado a lado" >> não é garantido pela hipótese de indução... Para mim a H.I. é "Todo >> grafo de k vértices, todos de grau >= k/2, possui um ciclo". Você quer >> um "quase-ciclo", e você pede um pouco menos do que grau >= k/2. Pode >> ser a mesma coisa, eu só não tenho certeza, e confesso que não tive >> tempo para pensar nisso essa semana. Se for mesmo, eu me desculpo de >> ser tão Bourbakista aqui. >> >> > []'s >> > Rogerio Ponce >> >> Abraços, >> -- >> Bernardo Freitas Paulo da Costa >> >> ========================================================================= >> Instruções para entrar na lista, sair da lista e usar a lista em >> http://www.mat.puc-rio.br/~obmlistas/obm-l.html >> ========================================================================= >> > > -- Abraços, Pedro.
