Answer to Question #81202 in Discrete Mathematics for Imran

Question

a) Let A be an 8×8 Boolean matrix (i.e. every entry is 0 or 1). If the sum of the entries in A is
51, prove that there is a row i and a column j in A such that the entries in row i and in column j
add up to more than 13. Further, show that there are at least 4 such pairs of rows and
columns.
b) If a planar graph has the degree sequence {2,2,3,3,4,4,4}, how many faces will it have? Draw
a planar graph with this degree sequence and number the faces to check your answer.
c) Give the order and the degree of the recurrence
a
2
n+2 = a
2
n +2an +4
Is the recurrence homogeneous?