\[type:CCC\]

    4.  Add the following row 3 times: $\langle 0, u, Z\rangle$. \[type:DDD\]

    5.  Add the following row 3 times: $\langle 0, Z, u\rangle$. \[type:EEE\]

2.  For each edge $(x, y)$, add two rows $\langle 0, x, y\rangle$ and $\langle 0, y, x\rangle$. These are called [*edge rows*]{}.

3.  Add the following two sets of [*dummy rows*]{}:

    1.  Add seven rows as below: $\langle 0, ?, Z\rangle$. \[type:DDD-A\]

    2.  Add seven rows as below: $\langle 0, Z, ?\rangle$. \[type:DDD-B\]

This completes the construction of the table. The privacy parameter is set as $k=7$.

Consider any $k$-anonymization solution to the constructed table. For any row of the table, we can derive a lowerbound on the cost paid by the row; we refer to the lowerbound as the [*base cost*]{}. The base costs are derived as follows, for the various types of rows. Consider any vertex $u\in V$. First consider rows of type \[type:AAA\]. These rows are of the form $\langle 0, u, u\rangle$ and there are exactly six of them. Since $k=7$, these rows must be participating in a cluster having a different row. Hence, each of these rows must pay a cost of at least 1. We set the base 