0
$\begingroup$

I'm reading Van Lint and Wilson: A Course in Combinatorics.

There is one part of the book where he defines a finite graph:

A graph is finite when both E(G) and V (G) are finite sets.

Theorem 1.1. A finite graph G has an even number of vertices with odd valency.

Reading it further, there is:

Theorem 1.2. A finite graph G with no isolated vertices (but possibly with multiple edges) is Eulerian if and only if it is connected and every vertex has even degree.

It was first said that a finite graph has an odd valency at each vertex, now a finite graph with every vertex with even degree is presented. How should I proceed? Should I drop the condition given in the first theorem (odd valency)? Does Eulerian graph mean a finite graph without this condition? I believe it is, but I want to be sure.

$\endgroup$

2 Answers 2

Reset to default
3
$\begingroup$

The confusion is that you read the theorem the following way:

A finite graph G has an even number of vertices, each with odd valency.

What the theorem states actually is:

A finite graph G has an [even number of vertices with odd valency].

Or, to make it more clear:

Theorem In a finite graph, the number of vertices which has an odd valency is even.

$\endgroup$
5
  • $\begingroup$ Now I get it. It could - for example - have 15 vertices but only two of them having odd valency. Now I understand. $\endgroup$
    – Red Banana
    Aug 29, 2014 at 14:33
  • $\begingroup$ @VladimirPutin Yes. The Theorem is probably not stated the best way, it could be read both ways. $\endgroup$
    – N. S.
    Aug 29, 2014 at 14:33
  • $\begingroup$ Take this example, is it a finite graph? It has an even number of vertices with odd valency, but it also has an odd number of vertices with odd valency. $\endgroup$
    – Red Banana
    Aug 29, 2014 at 14:49
  • $\begingroup$ @VladimirPutin Finite means that the number of vertices and edges are finite. So yes. An example of a graph which is not finite is the following: Vertices are the whole numbers, and edges are the pairs of consecutive numbers. $\endgroup$
    – N. S.
    Aug 29, 2014 at 14:53
  • $\begingroup$ @VladimirPutin In general, if you can draw all vertices and all edges it means it is finite..... $\endgroup$
    – N. S.
    Aug 29, 2014 at 14:53
3
$\begingroup$

Where does it say that a finite graph has an odd valency at each vertex? I see it saying the number of such vertices is even. Note that zero is an even number. There is no contradiction here.

$\endgroup$
5
  • $\begingroup$ Even number of vertices with odd valency. Doesn't it mean that each vertex has odd valency? $\endgroup$
    – Red Banana
    Aug 29, 2014 at 14:11
  • $\begingroup$ No, it means that the number of vertices with odd valency is one of 0, 2, 4, 6, 8, … (The result comes from the fact that each edge has two ends, so the total number of ends of edges is even.) $\endgroup$
    – Harald Hanche-Olsen
    Aug 29, 2014 at 14:15
  • $\begingroup$ @VladimirPutin If a graph has $3$ vertices, can that Theorem say that ALL vertices have odd valency? $\endgroup$
    – N. S.
    Aug 29, 2014 at 14:19
  • $\begingroup$ @N.S. But if it has 3 vertices, can it still be called a finite graph? $\endgroup$
    – Red Banana
    Aug 29, 2014 at 14:20
  • $\begingroup$ @VladimirPutin Well three vertices and 2 edges are a finite graph.... $\endgroup$
    – N. S.
    Aug 29, 2014 at 14:26

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .