Maximum connected components after removing 2 vertices

466 Views Asked by At

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.

1

There are 1 best solutions below

0
On BEST ANSWER

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.