1
$\begingroup$

Let $G=((2,3,4,5,6,7),E)$ be a graph such that {$x$,$y$} $\in E$ if and only if the product of $x$ and $y$ is even, decide if G is an Eulerian graph.

My attempt

I tried to plot the graph, this is the result:

enter image description here

So, if my deductions are true, this is not an Eulerian graph because it's connected but all the vertices doesn't have an even degree. For example $deg(2)=5$. Moreover, there is no trace of Eulerian trails.

I cannot figure out if this assumptions are presumably correct.

$\endgroup$
0

2 Answers 2

Reset to default
3
$\begingroup$

You don't need to draw the graph --- you can easily do this analytically.

You have 3 odd-numbered vertices and 3 even-numbered vertices. A product $xy$ is even iff at least one of $x,y$ is even.

A graph has an eulerian cycle iff every vertex is of even degree. So take an odd-numbered vertex, e.g. 3. It will have an even product with all the even-numbered vertices, so it has 3 edges to even vertices. It will have an odd product with the odd vertices, so it does not have any edges to any odd-numbered vertices. So $3$ has an odd degree, violating the necessary condition for an Eulerian graph. So G is not Eulerian.

$\endgroup$
1
  • $\begingroup$ @egreg Read Newb's answer again. He did not say odd degree vertices, he said odd numbered vertices. The three odd numbered vertices are $3,5$, and $7$. $\endgroup$ Commented Jan 28, 2014 at 17:49
1
$\begingroup$

I assume you meant the product is even based on the picture you have drawn. Your conclusions are correct for the drawn graph. It is connected and there are vertices of odd degree so it is not Eulerian.

$\endgroup$
7
  • $\begingroup$ There are more than two vertices with odd degree. $\endgroup$ Commented Jan 28, 2014 at 17:06
  • $\begingroup$ Which is irrelevant for the theorem being used. For connected graphs, if there are any odd degree vertices, then it is not Eulerian. $\endgroup$ Commented Jan 28, 2014 at 17:09
  • $\begingroup$ It depends on the definition: there exists a path that uses up all sides exactly once if and only if the number of odd degree vertices is $0$ or $2$. $\endgroup$ Commented Jan 28, 2014 at 17:12
  • $\begingroup$ True but Eulerian graphs are defined as having an Euler circuit not a Euler path. $\endgroup$ Commented Jan 28, 2014 at 17:13
  • $\begingroup$ Again, it depends on the definition you use; there's no law that prescribes "cycle" and not "path". Some texts use "path" (in Italy, at least). $\endgroup$ Commented Jan 28, 2014 at 17:17

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.