251.3 Graphs Arising from Other Structuresa) How are the incidence graphs of H and H* related?b) Show that the dual of H* is isomorphic to H.c) A hypergraph is self-dual if it is isomorphic to its dual. Show that the Fanoand Desargues hypergraphs are self-dual1.3.7HELLYPROPERTYAfamily of sets has the Helly Property ifthe members ofeach pairwise intersectingsubfamily have an element in commora)Showthatthefamily of closed intervals on thereal linehas theHellyProperty(E. HELLY)b) Deduce that the graph in Figure 1.20 is not an interval graph.Fig. 1.20. A graph that is not an interval graph1.3.8 KNESER GRAPHLet m and n be positive integers, where n > 2m. The Kneser graph KGm,n isthe graph whose vertices are the m-subsets of an n-set S, two such subsets beingadjacent if and only if their intersection is empty. Show that:a) KGi,n= Kn, n ≥3,b) KG2.n is isomorphic to the complement of L(Kn), n ≥ 51.3.9 Let G be a simple graph with incidence matrix M.a) Show that the adjacency matrix ofits line graph L(G) is M'M-2I, whereIisthem xmidentitymatrix.b) Using the fact that M'Mis positive-semidefinite, deduce that:i) each eigenvalue of L(G) is at least2,ii) if the rank of M is less than m, then -2 is an eigenvalue of L(G)-1.3.10a) Consider the following two matrices B and C, where is an indeterminate, Mis an arbitrary n x m matrix, and I is an identity matrix of the appropriatedimension.B - [M MC.- [-M]1.3 Graphs Arising from Other Structures 25 a) How are the incidence graphs of H and H∗ related? b) Show that the dual of H∗ is isomorphic to H. c) A hypergraph is self-dual if it is isomorphic to its dual. Show that the Fano and Desargues hypergraphs are self-dual. 1.3.7 Helly Property A family of sets has the Helly Property if the members of each pairwise intersecting subfamily have an element in common. a) Show that the family of closed intervals on the real line has the Helly Property. (E. Helly) b) Deduce that the graph in Figure 1.20 is not an interval graph. Fig. 1.20. A graph that is not an interval graph 1.3.8 Kneser Graph Let m and n be positive integers, where n > 2m. The Kneser graph KGm,n is the graph whose vertices are the m-subsets of an n-set S, two such subsets being adjacent if and only if their intersection is empty. Show that: a) KG1,n ∼= Kn, n ≥ 3, b) KG2,n is isomorphic to the complement of L(Kn), n ≥ 5. 1.3.9 Let G be a simple graph with incidence matrix M. a) Show that the adjacency matrix of its line graph L(G) is Mt M − 2I, where I is the m × m identity matrix. b) Using the fact that Mt M is positive-semidefinite, deduce that: i) each eigenvalue of L(G) is at least −2, ii) if the rank of M is less than m, then −2 is an eigenvalue of L(G) . ————— ————— 1.3.10 a) Consider the following two matrices B and C, where x is an indeterminate, M is an arbitrary n × m matrix, and I is an identity matrix of the appropriate dimension. B :=  I M Mt xI  C :=  xI −M 0 I