Question about König's Theorem for bipartite graphs

176 Views Asked by At

Does König's Theorem imply that the independence number of a bipartite graph is equal to the minimum number of cliques that cover all vertices?

König's Theorem states that the size of a maximum matching in a bipartite graph $G$ is equal to the size of a minimum vertex cover of $G$. I know that the complement of a minimum vertex cover is a maximum independent set, but is there a relationship between minimum number of cliques that cover all vertices and the size of a maximum matching?

It seems to me that for bipartite graphs, there can only be two-vertex cliques, and so a clique would be equivalent to a matching. Is this correct?

1

There are 1 best solutions below

0
On BEST ANSWER

You're right about biparte graphs having at most $2$ vertices in a clique.

Proof: Suppose that there is a clique of at least $3$ elements, $u_i$ ($i\in[3]$) then $u_1u_2u_3u_1$would be a cycle of odd length, which can't happen in biparte graphs.

Now, as you mentioned, there is an easy bijection between a matching $M\subseteq E(G)$ and $2$-cliques. However sometimes you need $1$-cliques to cover all the vertices, namely when $G$ doesn't have a perfect matching (e.g take $V=\{1,3\}\cup\{2\}$, $E=\{(1,2), (3,2)\}$). In general you can have an arbitrary amount of $1$-cliques needed to cover the vertices in a biparte graph.

Let the size of the minimum vertex covering be $\tau(G)$, the size of the maximum matching be $a_E(G)$, the minimum number of cliques that cover all vertices be $\theta(G)$ and the independence number be $a(G)$.

König tells us that $\tau(G) = a_E(G)$ and you mentioned that $\tau(G)+a(G) = |G|$. We noticed that $\theta(G) = a_E(G) + r(G)$, where $r(G)$ is the number of $1$-cliques in the minimum clique vertex cover.

Notice that $|G| - \theta(G) = a_E(G)$ (there are $2$ nodes for every $2$-clique and $1$ node for $1$-cliques, so the latter cancels out in the subtraction and we are left with the count of $2$-cliques). This equation uncovers the result

\begin{align} |G| - \theta(G) = a_E(G) &\iff |G|-a_E(G) = \theta(G) \\ &\iff |G|-\tau(G) = \theta(G) \\ &\iff a(G) = \theta(G) \end{align}