Sufficient condition for biconnectivity

67 Views Asked by At

Assume we have a planar graph $G$ with $2n+1$ vertices and $3n$ edges, such that it is bipartite $G=A\cup B$ and every vertex from $A$ is of degree $\leq 3$. Does it suffice to conclude that $G$ is a biconnected graph?

or guide me to the conditions from literature so that I can write what I have tried.

2

There are 2 best solutions below

2
On BEST ANSWER

No, this is not true.

Consider the graph on $7=2\cdot3+1$ vertices $\{A,b,C,D,e,f,G\}$ with edges

  • $A\sim b$;
  • $b\sim C,D$;
  • $C,D\sim e,f$; and
  • $e,f\sim G$.

This has $1+2+4+2=9=3\cdot3$ edges and a bipartition is $\{\text{upper-case}\}\sqcup\{\text{lower-case}\}$. Moreover, every vertex has degree at most $3$.

But removing $b$ disconnects the graph into $\{A\}$ and $\{C,D,e,f,G\}$.

4
On

Such a graph does not even need to be connected. For example, the disjoint union $K_{4,2} \sqcup K_{5,2}$ satisfies your hypotheses: it's planar, it has $13=2\cdot 6+1$ vertices and $18 = 3\cdot 6$ edges, and if we put the larger half of each component in $A$, then each vertex in $A$ has degree $2$.

(We can add an edge between an $A$-vertex in $K_{4,2}$ and a $B$-vertex in $K_{5,2}$, and delete an old edge, to get a counterexample that's connected but not biconnected.)