K-regular bipartite

Question

Draw a simple bipartite 3-regular graph with a cut vertex . Its easy to draw 3-regular bipartite graph.but, how about drawing it with a cut vertex ..Is there any possibility of that type of graph ..??How can we proceed ?

Answer 1

First note that a $3$-regular graph has a cut vertex iff it has a bridge (cut edge). If $v$ is a cut vertex of $G$, let $G'$ be the graph obtained by removing $v$ from $G$. Then $G'$ has two or three connected components; in either case, there is a component $C$ with exactly one vertex $v'$ which is adjacent to $v$ in $G$. Since $G$ is $3$-regular, there exists some vertex $w$ in $C$ which is adjacent to $v'$. For any such $w$, the path from $w$ to $v$ in $G$ contains $v'$, so $v'$ is a cut vertex and hence $vv'$ is a bridge.

Now, suppose $G$ has a bridge $e=uv$. Let $H$ be the graph obtained by removing $e$ from $G$, then $H$ has two connected components $C_1$, $C_2$ which each contain exactly one of $u$ and $v$. Suppose that $u\in C_1$. As a subgraph of a bipartite graph, $C_1$ itself is bipartite. Let $(V_1, V_1')$ be a bipartition of $C_1$ with $u\in V_1$. Then $$ \sum_{w\in V_1} \deg w = 3(|V_1|-1) + 2 \tag1 $$ and $$ \sum_{w\in V_1'} \deg w = 3|V_1'|.\tag2 $$ Since $C_1$ is bipartite, both $(1)$ and $(2)$ count twice the number of edges in $C_1$. But these quantities cannot be the same, as one is divisible by three and the other is not; hence, contradiction. We conclude that a $3$-regular bipartite graph cannot have a cut vertex.