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 > ========================================================================= >
