# 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.

## 1 Answer

Vertices are "joined" if there is a path between them. In our image there are two rings (0,2,4,6,8) and (1,3,5,7,9) which are connected.

Does the graph have an euler circuit? You can't get from an odd number to an even number, so no.

• So the subgraphs (0, 2, 4, 8) and (1, 3, 5, 7) are both considered "connected"? – Ogen Nov 6 '13 at 4:09
• @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
• dang, my bad. You always seem to be there to catch my mistakes. Thanks a bunch @BrianM.Scott – Jorge Fernández Hidalgo Nov 7 '13 at 2:25
• You’re welcome (and +1). – Brian M. Scott Nov 7 '13 at 9:35