Q3 Matemática (KoMaL A Problems 2021)
Em um grafo finito, simples e conexo jogamos o seguinte jogo: inicialmente colorimos todos os vértices com uma cor diferente. Em cada etapa, escolhemos um vértice aleatoriamente (com distribuição uniforme), e depois escolhemos um de seus vizinhos aleatoriamente (também com distribuição uniforme) e o colorimos com a mesma cor do vértice originalmente escolhido (se os dois vértices escolhidos já tiverem da mesma cor, não fazemos nada). O jogo termina quando todos os vértices tiverem a mesma cor. Conhecendo o grafo encontre a probabilidade para cada vértice de que o jogo termine com todos os vértices tendo a mesma cor do vértice escolhido.