Re: Eulerian Graph

From: Tim Brauch (RnEeMwOs.pVoEst_at_tbrauch.cNOoSPAMm)
Date: 10/07/04 

Date: Thu, 07 Oct 2004 05:30:53 GMT

"Romm" <nospam@nono.com> wrote in news:4164c967$1_3@aeinews.:

> I'm just wondering if a graph containing only one vertex is considered
> to be Eulerian ?
>
> Or if you prefer : G={X,A} is a non-oriented graph G where X is a set
> of vertices and A is a set of edges then
>|X| = 1 and A is an empty set
>
> By definition, an eulerian graph is a graph containing an eulerian
> circuit. An eulerian circuit (iff degrees of all vertices are even)
> contains an eulerian trail (visiting each edge one and only one time)
> and then comes back to the starting vertex.
>
> So in a case where my graph contains only one vertex, I do satisfy the
> conditition of not having odd degrees and I do not visit any edges
> more than once (well there is none)....but I somehow doubt that in a
> simple graph I can form a circuit just by having one vertex...any help
> ?

Depends on your definitions. I think, just my opinion, the definitions for
graph theory are still being pounded out. Although from what I've looked
up, they do seem to be standardizing with newer texts.

For example, one text I used defined a graph as a set of vertices and a set
of edges between the vertices. This definition allowed for multiple edges,
loops, and even unconnected graphs. A simple graph, by this text, was a
connected graph with no loops or multiple edges.

Another text defined a graph as a set of vertices an a set of edges such
that no edge was between the same vertex (no loops) and the edge set did
not contain repetition of elements (no repeated edges). There was also
something in there about being connected. I believe it used the term
general graph or something similar is multiple edges were allowed and
multigraph for an unconnected graph.

And the point of this? You need to check what you are using for the
definition of a circuit and path. If your definition states a non-empty
ordering of the edges, then you are out of luck. If however, nonempty is
not stated, then I think a single vertex will qualify.

 - Tim 

-- 
Timothy M. Brauch
NSF Fellow
Department of Mathematics
University of Louisville
email is:
news (dot) post (at) tbrauch (dot) com

Relevant Pages

  • Re: help.. making an undirected graph directed...
    ... >> A finite graph G is Eulerian if and only if all its vertex degrees are ... >> odd degree, it can't be Eulerian. ... an Eulerian path in a graph is a path that uses each ...
    (comp.programming)
  • Re: Eulerian path in infinite graph
    ... > asks for the reader to show that the infinite square grid is an Eulerian ... > graph by showing an explicit two-way Eulerian path (i.e., ... > covers every edges of the graph and that extends in both directions). ... Hint: spiral. ...
    (comp.theory)
  • Re: help.. making an undirected graph directed...
    ... > Could someone help me solve the following problem: Given a graph G, ... > directioning which has to be done. ... A finite graph G is Eulerian if and only if all its vertex degrees are ... except that for u!= v the edge leaving u in T must come ...
    (comp.programming)
  • Re: help.. making an undirected graph directed...
    ... >> A graph with exactly two vertices of odd degree has an Eulerian path, ... > A graph is called Eulerian if it contains an Eulerian circuit. ...
    (comp.programming)
  • Re: number combinations of components
    ... >>>yeah, if one considers them distinct it would be 8. ... The background for this is graph theory, where a graph G consists of a ... but there are many cases where the phase will produce a circuit that ... > I want all the ways to compose these functions. ...
    (sci.math)