Consider any $A \times B$ matrix $M$ whose entries are either $0$ or $1$. For $r \in \{1, ...., A\}$ and $c \in \{1, ...., B\}$, we denote by $M_{r,c}$ the entry of the matrix in row r and column c.
Definition: We say that the matrix $M$ is $k$-picky if, for every set $C \subseteq \{1, ...., B\}$ with $|C| = k$, for every $c \in C$, there is a row $r$ of $M$ such that $M_{r,c} = 1$ and, for each $q \in C - {c} $, we have $M_{r,q} = 0$. For this question, consider a network of nodes represented by a graph. Each node has a unique identifier in the range $\{1, ...., B\}$. In each time step $t$, a node $v$ has two choices: it can choose to transmit a message, or stay silent. If $v$ transmits a message in time step $t$, then its signal reaches all of its neighbours in the graph. If, in time step $t$, a node $w$ stays silent and has exactly one neighbour $v$ that transmits in time step $t$, then $w$ receives the message sent by $v$. If $w$ transmits in time step $t$, or has two or more neighbours that transmit in time step $t$, then $w$ does not receive any message. Suppose that every node in the network has at most $\Delta$ neighbours.
Suppose we give each node in the network the same $A \times B$ matrix $M$ whose entries are either $0$ or $1$. Each node runs the following algorithm $A_M$: in time step $t$, the node looks at entry $M_{t,i}$, where $i$ is the node's unique identifier. If $M_{t,i} = 1$, then the node with identifier $i$ transmits a message in time step $t$, and if $M_{t,i} = 0$, the node with identifier $i$ stays silent in time step $t$. We want to choose a matrix $M$ such that, if the nodes execute the above algorithm, it is guaranteed that every node receives a message from each of its neighbours. Explain how to use a $k$-picky matrix $M$ to provide this guarantee: give an appropriate value for $k$ and prove that the resulting algorithm $A_M$ guarantees that every node receives a message from each of its neighbours.
Pick any $\Delta$-picky matrix as $M$. The rest follows directly from the definitions.