# Homework -graph theory

Consider the undirected graph defined as follows. The vertex set is $\{0,1,2,3,4,6,7,8,9\}.$ The edges set $E$ is $$E=\{\{0,2\},\{2,4\},\{4,6\},\{6,8\},\{8,0\},\{1,3\},\{3,5\},\{5,7\},\{7,9\},\{9,1\}\}.$$ Do the following:

$\text{(a)}\,\,$Draw this graph.

$\text{(b)}\,\,$Write down the degrees of vertices $4$ and $3$.

$\text{(c)}\,\,$ How many components does this graph have?

$\text{(d)}\,\,$Write down all the components of the graph.

$\text{(e)}\,\,$Does the graph have an Euler circuit?

Here is my answer for $\text{(a)}$:

For $\text{(b)}$ I got $2$ and $2$.

For $\text{(e)}$ I got no because you can't visit all edges exactly once while starting and stopping on the same vertex.

But I am confused with $\text{(c)}$ and $\text{(d)}$. I googled that a component of a graph is a subgraph that is connected and is not contained in any other connected subgraph which has more edges or vertices than it. The definition of connected said every pair of vertices must be joined. I don't see that in the above graph. Any help would be appreciated.

• @Clay: Omnitic accidentally omitted one vertex from the first component: the components are $\{0,2,4,6,8\}$ (with associated edges) and $\{1,3,5,7,9\}$ (with associated edges). You can redraw the graph as two disjoint pentagons. – Brian M. Scott Nov 6 '13 at 11:09