Let a 3 regular, 2 connected (but not 3 connected) , bipartite, planar graph. After removing 2 vertices, how many connected components can there exist at most? I have created an instance with 3 (below). Is it the maximum? Is it the only case where this happens?

enter image description here

If we remove, the 2 red vertices, all the blue edges disappear and the graph has 3 connected components.


If $G - \{u,v\}$ has components $G_1, G_2, \dots, G_k$, then each $G_i$ must have an edge to both $u$ and $v$ somewhere: if $G_i$ did not have an edge to $u$, for example, then merely deleting $v$ would make $G_i$ disconnected from the rest of $G-\{v\}$, so $G$ would not be $2$-connected.

This requires both $u$ and $v$ to have degree at least $k$. Conversely, if $\deg u = \deg v = 3$, then $G - \{u,v\}$ can have at most $3$ components.

Your example shows that $3$ is possible, so $3$ is the maximum. For a more specific example, consider the graph below:

example graph

Ignoring the rectangles and the colors on the edges, this is a $3$-regular planar graph; the vertex colors show that it is bipartite. The colors on the edges give an open ear decomposition that proves it is $2$-connected: take the red cycle, then the blue ear, then the orange ear, and then the dashed edges (as one-edge ears) in any order. Finally, deleting the two vertices in the black rectangle leaves three connected components: the ones in the red, blue, and orange squares.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.