Even though this is not a complete answer, there are enough elements in this posting that I think someone can use to show domotorp where not to look for a counterexample. I also want to separate it from the marginally useful clutter in the other post of mine. Recall that I am focused on showing every bipartite graph H with exactly 512 edges has a subset of vertices which yields G, our target of an induced subgraph of H with exactly 256 edges.

A useful fact: if n is a prime power, if M is a multiset of positive proper divisors of n with sum equal to n, then there is a submultiset M' of M with sum kn/p, where k and p are positive integers, k is less than p, and p is the prime dividing n. A corollary of this fact is that any positive number of independent vertices whose degree sum is at least 256 and whose neighbors have degrees which are precisely powers of 2 will have an induced subgraph G on precisely that set of independent vertices. Edit: so that the corollary reads correctly, assume a subgraph H of K_a,b with degree sum of the a vertices at least 256 and the degrees of the b vertices are appropriate powers of 2. Then G subgraph of K_a,b' exists as an induced subgraph of H. End Edit.

From the corollary we get that domotorp won't find any counterexample graphs H which are subgraphs of K_a,b for a=1 or a=2. Further, for a=3 or 4, there won't be any counterexamples because at least two of the independent vertices of H will have degree sum at least 256. However, I want to refine the case of a=4 a bit.

Let J be a subgraph of K_4,b with number of edges n = 256 + 3k for some nonegative integer k. Then J also has an induced subgraph G: remove the b vertices of degree 3 and whatever else is needed to achieve the target number of edges. If J has a wealth of degrees, remove vertices of degrees 1,2, or 4 until n=256+3k as above. Otherwise J has less than 264 edges or else the b vertices all have degree 3, with at most one exception which must be of degree 2. Now from the four independent vertices, remove from J that vertex which has smallest degree. The result will either have
less than 260 edges, or will have a b vertex of degree 1 or at least two of degree 2, or a single edge will be removed leaving a K_3,b subgraph. In the first case J had less than 350 edges, the second and third cases will yield the goal graph G, and the final case will yield no G unless b is at least 128. The upshot is that if J has more than 381 edges, it will have a target graph G as an induced subgraph.

I worried the case a=4 to bits for a couple of reasons: one is to establish that any H which is a subgraph of K_5,b will have four of the five independent vertices with degree sum more than 400 (and thus will not be a counterexample), and two is to put a Rube Goldbergian type cap on this post for a=6. This proof idea is neat, and might be extendible, but I am going to give others the chance to do it.

Let H be a subgraph with 512 edges and be a subgraph of K_6,b.
Note that if any two of the six independent vertices have degree sum at least 256 or any of those six has degree less than 12, I can turn to cases for a=2 and a=5 and assert that a target G exists.

I will now find four of the six vertices and hope that there is a G that uses those vertices. Note that we may assume the four vertices have degree sum at least 256.

First consider the degree sums of the six mod 3. The sum of the sums is 2=512 mod 3. Suppose two of the degrees mod 3 are 2. Then the remaining four have degree sum equal mod 3 to 256, so I can use that to produce G. So assume at most one of the six degrees is 2 mod 3. Then if there is one other nonzero degree mod 3, there is at least one which is zero mod 3, and those two I exclude from the four to get another degree sum equal mod 3 to 256, and again I get G. The remaining case that resolves nicely is if none are 2 mod 3, and again I can find G.

The last case is that one of the six vertices has degree 2 mod 3, and all the rest are 0 mod 3. Of the remaining 5, I can try to choose some subset of 4 and hope for that subgraph to not fall in the case where the multiset of b vertices foils me by having all threes or all threes and one two. But if I am so unlucky, then I take all 5 vertices to get a degree set with some fours or some ones, as well as some threes or twos (remember at least 12 degrees will be incremented, although some of them might have started at 0). So I can guarantee a multiset of degrees that allow the composition I want, and gain my prize graph G.

The things I do for bounty!

Gerhard "Wait Till You See Seven" Paseman, 2012.11.14

14more comments