Is impossible to put edges between $H_1$ and $H_2$ in such a way as to produce a $(3, 6)$-graph

Question

I need help with this problem of graph theory

Let $G$ be a $(3,6)$-graph on $17$ points with $39$ edges and $G$ have $7$ points of degree $4$ and $10$ points of degree $5$

Is possible to prove mathematically that is impossible to put edges between $H_1$ and $H_2$ in such a way as to produce a $(3, 6)$-graph, where degree of $p1$ is 5 ($d(p1)=5$), $d(p_2)=d(p3)=5$ and $d(p4)=4$

A point $p$ of $H_2$ which has exactly $j$ edges to $H_1$ will be called a $j$-point

In $G$ there are only $0$-points, $1$-points and $2$-point and there are only points of degree $4$ or $5$, also in $H_2$ there are $20$ edges.

Answer 1

I have proved this with the aid of a computer program. I spent quite a bit of time yesterday trying to prove it manually, but I just couldn't account for all the possible configurations. I've never attempted a problem like this before, so I'm just trying to do it from first principles, and there may be some simple argument I'm overlooking.

I will renumber the point to $p_0,p_1, p_2, p_3$ because I wrote a python script and python uses zero-based numbering. This will make the relation to my script clearer, I hope.

First, we note that the sets of vertices joined to any of $P=\{p_0,p_1, p_2, p_3\}$ must be independent, or we will have a triangle. Also, any set $S$ of $4$ independent vertices in $H_2$ must be joined to at least $3$ vertices in $P$, or two of the omitted vertices, together with $S$, will form an independent $6$-set.

It is easy to count that there are $34$ independent $4$-sets in $H_2$, and the program computes them. Let $S_i$ be the independent $4$-set joined to $p_i,\ i=0,1,2.$ If two of them are equal, say $S_0=S_1$, then neither of them can be joined to $p_2$ or $p_3$ since that would give a $3$-point, but then $S_0\cup\{p_2,p_3\}$ is an independent $6$-set. We conclude that $S_0,S_1,S_2$ are three distinct sets.

The program proceeds by considering each combination of three independent $4$-sets, and reject obvious impossibilities.

• We cannot have $S_0\cap S_1\cap S_2 \neq\emptyset$, for then there is a $3$-point.

• There cannot be an independent $3$-set $S$ in $\overline{S_0\cup S_1\cup S_2}$, for then $S\cup\{p_0,p_1,p_2\}$ is an independent $6$-set.

• If one is disjoint from both the others, say $S_0\cap(S_1\cup S_2)=\emptyset$, then $S_0\cup\{p_1,p_2\}$ is an independent $6$-set.

• Similarly, if any independent $4$-set is disjoint from two of $S_0,S_1,S_2$, we can construct an independent $6$-set.

At this point, the script rejects some symmetries. At least one point on the outer octagon must be included in $S_0\cup S_1\cup S_2$ and we can require $1\in S_0\cup S_1\cup S_2.$ Also, we can require that if any vertex on the outer octagon is joined to two of $\{p_0, p_1, p_\}$, then so is $1$.

It turns out that in all the remaining candidates, one of the $S_i$ intersects each of the other in one point, and the remaining two $S_i$ are disjoint, so that $|S_0\cup S_1\cup S_2|=10.$ I had spent a good deal of time unsuccessfully trying to prove this manually. Finally, I didn't use it at all, because it was awkward to take advantage of in the program, and there were few possibilities left, so brute force was indicated.

As candidates for $S_3$ the set of vertices joined to $p_3$ I took each set of three vertices not already joined to two points from $P$, rejecting those that weren't independent. Then I checked whether each independent $4$-set intersected at least three of the $S_i, i=0,1,2,3.$ All candidates were rejected, proving the impossibility.

Here is my script:

from itertools import combinations, product

H = set(range(1,13))
nbrs = {}
nbrs[1]={2,8,10}
nbrs[2]={1,3,9}
nbrs[3]={2,4,11}
nbrs[4]={3,5,10}
nbrs[5]={4,6,12}
nbrs[6]={5,7,11}
nbrs[7]={6,8,9}
nbrs[8]={1,7,12}
nbrs[9]={2,7,10,12}
nbrs[10]={1,4,9,11}
nbrs[11]={3,6,10,12}
nbrs[12]={5,8,9,11}

def independent(s):
    return all(a not in nbrs[b] for a in s for b in s)

indy = []
for c in combinations(H,4):
    if independent(c):
        indy.append(c)
assert len(indy) ==34

for c in combinations(range(len(indy)), 3):
    S = [set(indy[i]) for i in c]
    if S[0] & S[1] & S[2]:
        continue    # no 3-points
    # if S[0] disjoint from S[1} | S[2], then
    # S[0] | {p1, p2} is independent 6-set
    if S[0] & (S[1] | S[2] ) == set():
        continue
    if S[1] & (S[0] | S[2] ) == set():
        continue
    if S[2] & (S[1] | S[0] ) == set():
        continue
    comp = H - (S[0] | S[1] | S[2])
    # If u is an indendent 3-set in comp, then
    # u | {p0,p1,p2} is  an indendent 6-set
    if any (independent(s) for s in combinations(comp,3)):
        continue
    # if any independent 4-set is disjoint from 2 of
    # S[0, S[1], S[2] then we have an independent 6-set
    if any(len([s for s in S if s & set(i)==set()]) >= 2 for i in indy): 
        continue
    # symmetry rejection
    if 1 in comp:
        continue    
    T = list(S[0])+list(S[1])+list(S[2])
    T2 = [t for t in T if T.count(t)>1]
    if 1 < min(T2) < 9:
        continue
    # There are 10 points in S[0] | S[1] | S[2], so two of
    # these sets are adjacent to only 2 of the p-points
    # and so must be adjacent to p3
    assert len(comp) == 2
    # Try all possibilities for S[3]
    # No 3-points
    count = 0
    pop = H - ( (S[0]&S[1]) | (S[0]&S[2]) | (S[1]&S[2]) )
    for s3 in combinations(pop, 3):
        if not independent(s3):
            continue
        s3 = set(s3)
        # if any independent 4-set is disjoint from 2 of
        # S[0, S[1], S[2] , s3then we have an independent 6-set
        if any(len([s for s in S+[s3] if s & set(i)==set()]) >= 2 for i in indy): 
            continue  
        count += 1
        print(S, s3)
print(count, "solutions")

The script prints 0 solutions.