graph theory
Let's say I have a graph like this
How can I prove that this graph is planar(or non-planar)?
According to Kuratowski's theorem: Equivalently, a finite graph is planar if and only if it does not contain a subgraph that is homeomorphic to K5 or K3,3.
So I need to find if this graph containts subgraphs K(5) or K(3,3)?
And if I need to add few edges to make in non-panar, does it mean that I need to add edges to get either subgraph K(5) or K(3,3)?
Affirmed.
I offer the following (hopefully constructive) criticisms:
"We can see that the original graph has a subgraph homeomorphic to $K_{3,3}$ by redrawing it as follows: [[blah blah blah]]. Therefore it's not planar by Kuratowski's Theorem."
These were drawn using TikZ. Here's the LaTeX code:
\begin{tikzpicture}
\tikzstyle{vertex}=[circle,draw=black,fill=black!20,minimum size=18pt,inner sep=0pt]
\draw (0,0) node (c){};
\draw (c)++(0*360/4+135:3) node[vertex] (A){$A$};
\draw (c)++(1*360/4+135:3) node[vertex] (C){$C$};
\draw (c)++(2*360/4+135:3) node[vertex] (D){$D$};
\draw (c)++(3*360/4+135:3) node[vertex] (B){$B$};
\draw (c)++(0*360/4+135:1.5) node[vertex] (E){$E$};
\draw (c)++(1*360/4+135:1.5) node[vertex] (G){$G$};
\draw (c)++(2*360/4+135:1.5) node[vertex] (H){$H$};
\draw (c)++(3*360/4+135:1.5) node[vertex] (F){$F$};
\draw[ultra thick] (A) -- (B) -- (D) -- (C) -- (A);
\draw[ultra thick] (A) -- (E) -- (H) -- (D);
\draw[ultra thick] (B) -- (F) -- (G) -- (C);
\draw[ultra thick] (E) -- (G);
\draw (F) -- (H);
\end{tikzpicture}
and for the second drawing:
\begin{tikzpicture}
\tikzstyle{vertex}=[circle,draw=black,fill=black!20,minimum size=18pt,inner sep=0pt]
\draw (0,0) node (c){};
\draw (c)++(0,3)++(2,0) node[vertex] (G){$G$};
\draw (c)++(0,3) node[vertex] (A){$A$};
\draw (c)++(0,3)++(-2,0) node[vertex] (D){$D$};
\draw (c)++(-2,0) node[vertex] (E){$E$};
\draw (c) node[vertex] (C){$C$};
\draw (c)++(2,0) node[vertex] (B){$B$};
\draw (c)++(-2,1.5) node[vertex] (H){$H$};
\draw (c)++(2,1.5) node[vertex] (F){$F$};
\draw[ultra thick] (A) -- (B) -- (D) -- (C) -- (A);
\draw[ultra thick] (A) -- (E) -- (H) -- (D);
\draw[ultra thick] (B) -- (F) -- (G) -- (C);
\draw[ultra thick] (E) -- (G);
\draw (F) -- (H);
\end{tikzpicture}
Sedlacek has shown that a graph $G$ has a planar line graph if and only if $G$ is planar of maximum degree 4 and every vertex of degree 4 is a cut vertex. Using the result, Greenwell and Hemminger [2] proved a graph $G$ has a planar line graph if and only if $G$ has no subgraph homeomorphic to $K_{3,3}$, $K_{1,5}$, $P_4+K_1$, or $K_2+\bar{K}_3$.
[1] Sedlacek, J. "Some properties of interchange graphs." Theory of Graphs and its Application (1964): 145-150.
[2] Greenwell, D. L., and Robert L. Hemminger. "Forbidden subgraphs for graphs with planar line graphs." Discrete Mathematics 2.1 (1972): 31-34.
Best Answer
If you merge the two upper right vertices, and merge the two lower right vertices, you get $K_{3, 3}$. So the graph is not planar.
In general, you just have to search to see whether you can find $K_5$ or $K_{3,3}$, or whether you can find a planar embedding. I don't think there is some easy criterion that you can use to simply count up and conclude.