# can someone tell me if this graph contains subdivisions of both K5 and K3,3

Can someone tell me if this graph contains subdivisions of both $K_5$ and $K_{3,3}$ or not?

The graph G1134 is non-planar

My thought is that this graph subdivision of $K_{3,3}$ but not $K_5$. Is this correct? Please if there any help I will be thankful

-
My answer has been up for a week. Have you had a chance to look at it? Is it helpful? Any questions about it? – Gerry Myerson Feb 26 '14 at 12:13

## 1 Answer

Call the vertices, reading from top to bottom and left to right, $a,b,c,d,e,f,g$. Here's the adjacency matrix: $$\matrix{&a&b&c&d&e&f&g\cr a&0&1&1&0&0&0&0\cr b&1&0&0&1&1&1&1\cr c&1&0&0&1&1&0&1\cr d&0&1&1&0&0&1&1\cr e&0&1&1&0&0&1&1\cr f&0&1&0&1&1&0&1\cr g&0&1&1&1&1&1&0\cr}$$

Each of $b,c,f$ is adjacent to each of $d,e,g$, so there's a $K_{3,3}$. But there's also a $K_5$: consider the vertices $b,d,e,f,g$. Each one is adjacent to each of the others, except that $d$ and $e$ are not adjacent. But both $d$ and $e$ are adjacent to $c$, so $dce$ is a subdivision of $de$, and there's your $K_5$.

-