Let's suppose G is minimal counterexample. We are denote vertices as "x1 x2 x3 ..." xi={0|1} so, for example, "110...01" and "001...10" are antipodes. Consider G' is subgraph induced by x1=1. G' is lesser hypercube, so where exists connected pair of G'-antipodes, for clarification, "100001111" and "111110000". but ("100001111","000001111") and ("111110000","011110000" ) are edge-antipodes in G, so either ("100001111", "011110000") or ("000001111", "111110000") are connected! (And path length is equal to G dimension.)
Looks too simple, am I misunderstood something? Or where is my medal? :))
login/create account
Drupal
CSI of Charles University
proof?
Let's suppose G is minimal counterexample. We are denote vertices as "x1 x2 x3 ..." xi={0|1} so, for example, "110...01" and "001...10" are antipodes. Consider G' is subgraph induced by x1=1. G' is lesser hypercube, so where exists connected pair of G'-antipodes, for clarification, "100001111" and "111110000". but ("100001111","000001111") and ("111110000","011110000" ) are edge-antipodes in G, so either ("100001111", "011110000") or ("000001111", "111110000") are connected! (And path length is equal to G dimension.)
Looks too simple, am I misunderstood something? Or where is my medal? :))