3-Connected Planar Graphs and Cycles

Question

Some definitions:

$\textbf{$k$-connected}$: $G = (V, E)$ is called $k$-connected (for $k > \in \mathbb{N}$) if $|G| > k$ and $G-X$ is connected for every set $X \subseteq V$ with $|X| < k$.

Facts:

• If a graph is $3$-connected it is also $2$-connected
• In $2$-connected plane graph, every face is bounded by a cycle.

$\textbf{Theorem 1:}$ Show that if $u$ is a vertex in a $3$-connected planar graph, there is a cycle of the graph that contains the neighbors of $u$.

I was wondering if I can solve Theorem 1 using the Facts I described above. If so, I would like to know how I could argue. Or if there is any other way to show it

Answer 1

Yes, those facts suffice to prove Theorem 1.

Here's a hint:

If $G$ is 3-connected, then $G-u$ is 2-connected.

And some more:

Further, the vertex $u$ lies in a face $f$ of $G-u$ in the plane, and every neighbor of $u$ has to lie on the cycle bounding $f$ by planarity.

Answer 2

If I understand your question correctly, it might be preety straightfoward. Let me give you an idea:

Let $G$ be your 3-connected planar graph and let $v\in V(G)$. As you mentioned we have that $G$ is also 2-connected, which by Menger's Theorem gives us that there exist at least two independent paths between any two vertices of $G$. Obviously, this fact implies the existence of circuits containing $v$.

Let $C$ be a maximal circuit on $G$ containing $v$ and assume that there exists $w\in \text{Adj}(v)$ such that $w\not\in C$. In this case, we consider the 'last' vertex $u$ of $C$ and paths $P_1$ from $u$ to $w$ and $P_2$ from $w$ to $v$. Appending $P_1$ and $P_2$ to $C$, we obtain another circuit $\overline{C}$ which contains $C$. This contradicts our assumption that $C$ was maximal.

Try out checking the details!

P.S: I didn't see the relation of your proposition with planarity