Grafos Half Cut - Sucupira, Rubens A.; Klein, Sulamita; Faria, Luerbio (Anais do Encontro de Teoria da Computação (ETC), 2017)
[Erdös 1965] mostrou que todo grafo G = (V, E) com m arestas admite um corte de arestas com cardinalidade pelo menos m/2. Neste artigo definimos a classe de grafos Half Cut como os grafos que admitem um corte de arestas com cardinalidade igual a [m/2]. Nós também damos exemplos de grafos tais como caminhos, ciclos e grafos completos que devem satisfazer condições especiais para que sejam do tipo Half Cut.