LINEAR ALGEBRA GRAPH THEORY We define a graph H as follows t

****LINEAR ALGEBRA, GRAPH THEORY****

We define a graph H as follows: the vertices are subsets of size 2 of [11], so there are (11 2) = 55 vertices in the graph. Two vertices (sets) A and B are adjacent if and only if their corresponding sets satisfy the condition that |A intersection B| = 1 (note this is different from the Kneser graph!). This graph H contains 495 edges. The (multi)set of eigenvalues of H are {18^(1), 7^(10), (-2)^(44)}. The complete graph K_55 contains 1485 edges. Prove that the 1485 edges in K_55 cannot be decomposed into 3 copies of the graph H.

Solution

ANSWER:

we will use a result here (without proof),

We know that K_n has a decomposition into 3 isomorphic subgraph H if (n+1) is divisible by 3.

Here n=55, n+1=56 which is not divisible by 3 and so K_55 can not have decompostion of 3 copies of H.