Bipartite-Graph GCD question

Question

Let $G$ be a bipartite graph with bipartition $(A, B)$. Suppose every vertex in $A$ has degree $k_a$, and every vertex in $B$ has degree $k_b$. Prove that if $G$ has a bridge, then $\operatorname{gcd}(k_a,k_b) = 1$.

Answer 1

HINT: Take a look at the answer to this question, which proves that if $k_a=k_b>1$, $G$ has no bridge. The idea used in that answer can be combined with Bézout’s identity to yield your result.

Answer 2

PROOF SKETCH: First, let us write $c=\gcd(k_a,k_b)$.

Let us suppose $e$ is a bridge. Then let $X$ be a component of $G \setminus \{e\}$. Then $X=(A_1,B_1)$, where either (a) no vertex in $A_1$ is incident to $e$, or (b) no vertex in $B_1$ is incident to $e$; assume WLOG that no vertex in $A_1$ is incident to $e$, and thus exactly one vertex $b \in B_1$ is incident to $e$. Then for each vertex $v$ in $X$ let $d_X(v)$ be the number of neighbors in $X$ that $v$ has.

Then on the one hand, because $e$ is a bridge and no vertex in $A_1$ is incident to $e$, every vertex in $A_1$ has exactly $k_a$ neighbors in $X$, so $d_X(a)=k_a$ for each $a \in A_1$, which gives $\sum_{a \in A_1} d_X(a) = k_a|A_1|$. That $G$ is bipartite implies that $X$ is bipartite as well, so $k_a|A_1| = \sum_{a \in A_1} d_X(a) = \sum_{b \in B_1} d_X(b)$, giving

$$k_a|A_1| = \sum_{a \in A_1} d_X(a) = \sum_{b \in B_1} d_X(b).$$

Thus, as

$$\sum_{v \in X_1} d_X(v) = \sum_{a \in A_1} d_X(a) + \sum_{b \in B_1} d_x(b)$$

it follows that $$2k_a|A_1| = \sum_{v \in X} d_X(v).$$

And so (A) $c$ divides $\sum_{v \in X_1} d_X(v)$.

However, on the other hand, there is exactly one vertex $b$ in $X$ that satisfying $c \not | d_X(b)$, namely the vertex $b \in B_1$ incident to $e$; that vertex $b$ satisfies $d_X(b)=k_b-1$. Thus,$c$ cannot divide $\sum_{v \in X_1} d_X(v)$, which gives a contradiction from (A).

---

NB: This result also holds for $G$ bipartite even if we weaken to there is an integer $c \ge 2$ s.t. $c|d_G(v)$ for all vertices $v \in G$. If $c$ is even then $G$ does not even have to be bipartite.

HOWEVER, there are 3 regular graphs with a bridge; take two copies of $K_4$, subdivide one of the edges in each copy and put an edge between the two resulting vertices.