[seqfan] Re: graphs with odd degrees

Jonathan Post jvospost3 at gmail.com
Sun Apr 8 03:05:37 CEST 2012

A simple graph, also called a strict graph (Tutte 1998, p. 2), is an
unweighted, undirected graph containing no graph loops or multiple
edges (Gibbons 1985, p. 2; West 2000, p. 2; Bronshtein and Semendyayev
2004, p. 346). Unless stated otherwise, the unqualified term "graph"
usually refers to a simple  graph.


Gibbons, A. Algorithmic Graph Theory. Cambridge, England: Cambridge
University Press, 1985.

Tutte, W. T. Graph Theory as I Have Known It. Oxford, England: Oxford
University Press, 1998.

On Sat, Apr 7, 2012 at 5:44 PM, David Wilson <davidwwilson at comcast.net> wrote:
> It is clear that we cannot allow repeated edges, since then there would be
> an infinite number of 2-vertex graphs (any graph in which the two vertices
> are connected by an odd number of edges). So we should probably mention that
> repeated edges are verboten.
> Don't we need to specify that edges cannot be duplicated?
> The 1 counts the 2-vertex graphs, specifically the complete graph.
> The 3 counts the 4-vertex graphs, which would include the complete graph,
> the tree with root of order 3, and the disconnected graph consisting of two
> complete 2-vertex graphs. So we should probably mention that disconnected
> graphs are permissible.
> I would feel better if someone could draw out the 16 graphs on 6 vertices.
> On 4/6/2012 9:59 AM, Neil Sloane wrote:
>> The convention in the OEIS is that if a sequence
>> has every other term zero, we omit the zeros.
>> So the OEIS version of this sequence should be
>> 1,3,16,243,...
>> Neil
> _______________________________________________
> Seqfan Mailing list - http://list.seqfan.eu/

More information about the SeqFan mailing list