On a problem of C. Berge
Chong-Yun Chao · Proceedings of the American Mathematical Society · 1963
The unsolved problem, number 4 on page 251 in [1 ] states: Does the sum of two graphs have a kernel (French: noyau) if each of them has a kernel?. The purpose of this note is to give a negative answer. The definitions and notations used here are the same as in [1]. Let G1= (X1, r1) where X1= {Xl, X2, X3, X4}, and rlix= I{X2, X4}, rl1X2 = { X8, X4 }, r1x3 = { X1, X4 } and r1x4 = 0. Also let G2= (X2, r2) where X2= { yl, Y2} and r2y1= { Y2} and r2y2= 0. Clearly, G1 has a kernel, namely { X4 }, and G2 has { Y2} as its kernel. Form G = G1 + G2 = (X1XX2, r). We claim that G does not have a kernel. Suppose G had one, denoted by S, then (X4, Y2) must belong to S, because r(x4, y2) = 0. By definition of S, none of the nodes in r-i(x4, Y2) = { (X1, Y2), (X2, Y2), (X3, Y2), (X4, Y2) } can be in S. The rest of nodes of X1XX2, (xl, Y1), (X2, yi) and (x3, yi), generate a complete subgraph (it is also an odd directed cycle), only one of them can be in S. But, no matter which one of them is in S, there is always another one, (x, y), of them which has the property rI(x, y)C\S= 0 where (x, y) EES. This is a contradiction to the definition of S. Hence, G goes not have a kernel. Similarly, one can construct a family of such graphs: Take G( to be a complete directed graph of n nodes (n > 3) with a Hamiltonian cycle (or take G' to be a directed cycle of n nodes where n is odd and >1), and take G1 to be G J {I xn+1 } such that from every node of G' there is a directed edge toward the node xn+i and no edge leads from x,+1. Take G2 as before. Then each of G1 and G2 has a kernel, but G= G1+G2 does not have one by the similar argument as before.