0
$\begingroup$

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)}$:

enter image description here

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.

| cite | improve this question | |
$\endgroup$
2
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.