Berge: Theory of Graphs

It seems that the concept of incidence matrix was started by Kirchoff.

Representation of a graph: A graph can be represented as a pair (X,Gamma) or (X,U). Gamma is a function from X -> X. This encodes multi-graphs and infinite graphs (if we allow Gamma to be a multi-function). U is a subset of the possible arc sets. If U is a symmetric set, then the graph is undirected.

Chapter 3

Core concept: bounded is different from finite. Finite is different from infinite.

If a set has bounded number of elements, its cardinality is finite and not infinite.
If a set has unbounded number of elements, its cardinality could be finite, or infinite.
If a set has finite-unbounded number of elements
A good example is the 1-d graph which starts at origin and extends unboundedly towards right. Each node on the graph has edges to its immediate left neighbour and all the nodes to its left. For such a graph, the outdegree of any given vertex is unbounded. Still it is finite!!!

Also, a set could have unbounded number of elements and still be finite.

Finite Graphs: A graph is called finite if |X| is finite.

[If there exists a function that maps a vertex of the graph to a natural number, then the graph is not finite. Further, it is an infinite graph. Also, there seems to be many types of infinite graphs. However, Berge gives talks about certain types of infinite graphs meaning ones that satisfy some conditions, esp. the early theorems so that the results of finite graphs can be extended to those types of infinite graphs.]

Gamma-finite: A graph is Gamma-finite, if Gamma(x) < inf for all x in X. (This means that every vertex has finite number of edges out it.)

Gamma^-1-finite: A similar definition about Gamma^-1 rather than Gamma (Gamma^-1 is the inverse of the function Gamma.)

A graph is called locally finite if it is both Gamma-finite and Gamma^-1-finite. Also, a finite graph is locally finite.

Gamma-bounded: A graph is said to be Gamma-bounded if there exists a m such that Gamma(x)<=m for all x in X.

Progresssively finite: A vertex v is progressively finite if no paths of inf length start at v. A graph is progressively finite if is is progressively finite at each of its vertices. [see a note below about progressively finite and having no circuits.]

Progressively bounded: A graph is progressively bounded at vertex v if a number m exists such that the length of all paths starting from v is less than or equal to m. A graph is progressively bounded if it is progressively bounded at each of its points.

The relations regressively finite and regressively bounded are similar to the definitions of progressively finite and progressively bounded. The later deal with the graph (X,Gamma), while the former deal with the graph (X,Gamma^-1).

Relevant examples

RDG: An RDG is a finite graph. So it is Gamma-finite and Gamma^-1-finite. It is also Gamma-bounded and Gamma^-1 bounded. It is usually has cycles, as we deal with a strongly connected component of the RDG. So, it is not progressively bounded. Neither is it progressively finite. It is also not usually regressively bounded and not regressively finite.

EDG of a RDG defined across a finite domain: Such a graph is a finite graph. It is also Gamma-finite and also Gamma^-1 finite. It is also Gamma-bounded and Gamma^-1-bounded. It is progressively finite, if its associated SURE is computable and there exists a schedule. It is progressively bounded if the SURE has a bounded schedule. What about regressively bounded and regressively finite???

[actually the graph theoretic definitions preceed the definitions of computability and schedules. Here we will allow circular definitions.]

EDG of a RDG defined across the entire positive orthant: Such an EDG is an infinite graph. It is Gamma-finite and also Gamma^-1 finite. It is also Gamma-bounded and Gamma^-1 bounded. It is not progressively finite and so is not progressively bounded. It is also not regressively finite and so is not regressively bounded.

EDG of a RDG of a SARE defined over a finite domain: Such a graph is a finite graph. It is Gamma-finite, Gamma-bounded and so Gamma^-1-finite and Gamma^-1-bounded. It is progressively bounded, and progressively finite. It is regressively bounded and regressively finite.

EDG of a RDG of a SARE defined across the entire positive orthant: Such a graph is not finite. It is not Gamma-bounded. Neither is it Gamma^-1-bounded. It is Gamma-finite and Gamma^-1-finite.

I donot know about the computability conditions of either of the types of SAREs. So, no statements about the progressively.* and regressively.* for now.

Theorems

Theorem 1: If a graph is finite, the properties progressively finite, progressively bounded and 'without circuits' are equivalent.

[Note the implication of 'without circuits': If a graph is finite and it is progressively finite, it cannot have any circuits, as that will lead to having infinite path lengths beginning at any of the vertices participating in the circuit. A similar statement can be said about the progressively boundedness of a finite graph.]

Proof of therorem 1: Direct from applying the definitions to a finite graph.

[This proof is kind of easy, because, for a finite graphs |X| < inf. Also, if it does not have any circuits, there exists a bound on the maximum length of a path from each vertex. So, the graph is progressively bounded and is trivially progressively finite. As Berge himself says, infinite graphs are more interesting.]

Questions on the wording of theorem 1: Theorem 1 talks about the equivalence of 'progressively finite' and 'without circuits' for finite graphs. When are the properties not equivalent for infinite graphs?

[which of the 'progressively finite', 'progressively bounded' and 'without circuits' implies the other? It seems that 'progressively finite' combined with 'the graph is finite' is enough. The other two properties seem a little too strong.]

Answer: My current answer is the following: It does not seem that we can give a statement about all paths of an infinte graphs. Why not?
Answer 2: Is one of the conditions 'progressively finite' necessary for the other? and that the other is a sufficient condtion? Is it that the necessary condition and sufficient conditon are satisfied by finite graphs and only one of them is satisfied by infinite graphs?

Meaning of infinite path: What does an infinite path mean? When is a path infinite and when is it finite? Suppose we had just three vertices and a circuit along them, how many paths are there? Suppose we have an infinte number of vertices and the graph does not have loops and circuits. Does the graph have any infinite paths?? NO????? Are we getting confused between an infinite path [meaning a path of infinite length] and infinite number of paths?

Infinite sets: Here are two defs of infinite sets. 1 , 2.

A circuit induces an infinte number of paths on each of the vertices participating in it. Each of the infinite paths is of finite length. An infinte graph (for example the 1-d graph) has infinite number of paths, each of finite length. THEN WHAT IS AN INFINITE PATH? A path whose length is neither bounded by any integer nor there exists a finite number which can specity its length. What is such an example?

Theorem 2: If a graph is progressively finite and Gamma-finite, we have Gamma-hat(x) < inf for all x in X.

The theorem is kind of disturbing. This is because, it states that even in a graph with infinite number of nodes, it gives a statement about the cardinality of the set Gamma^hat. It says that the cardinality is a number, which is possibly unbounded. However, it is a finite number. See the definition of Gamma^hat.

Proof of theorem 2: Suppose the graph is progressively finite and Gamma-finite and that we had a vertex such that Gamma-hat(x)=inf. As the graph is Gamma-finite, x should be adjacent to a vertex x1 such that Gamma-hat(x1)=inf. by similar reasoning, x1 must be adjacent to x2 such that Gamma-hat(x2)=inf. etc... The path [x,x1,x2...] is therefore of inf length. Which contradicts that the graph is progressively finite.

Proof for necessity of theorem 1's premise: The method followed is proof by contradiction. The technique is the following: The theorem statement is of the form: A => B => C. With A being 'graph is Gamma-finite', B being 'graph is progressively finite', C being 'for all x in X, |Gamma^hat(x)| < inf '. B=>C is equivalent to NOT(B) OR C. We assume its contradiction is true; i.e., B AND NOT(C) is true and get a contradiction with A. proof method is: B and NOT(C) means, 'the graph is progressively finite' and 'there exists a vertex x (in X) such that |Gamma^hat(x)| = inf'. To get: contradiction with 'Gamma-finiteness of any vertex of the graph'.

let v be the vertex such that |Gamma^hat(x)| = inf. Let k be the number of paths out of v [objective: k is infinite] The graph is progressively finite meaning 'there exist no paths of infinite length' => all paths out of v are of finite length => There exists a path of maximum length (this is because, in a set of numbers of which infinity is not a member, we can always select an maximum). Then k*length_of_the_max_length_path is the upper bound on the number of vertices reachable by v. By hypothesis, this number is infinite.

Corollary 1: A Gamma-finite which is progressively finite at a vertex x0 is also progressively bounded at x0.

[The real punch line to this benign looking proof is applying the absolutely harmless looking theorem 1 to the subgraph induced by Gamma-hat(x) which happens to be finite.]

Proof of Corollary 1: The subgraph determined by the set Gamma^hat(x) is finite! So, applying the theorem1 to this subgraph, the terms 'progressively finite', 'progressively bounded' and 'without circuits' are equivalent.

[note the equivalence of 'without circuits' and 'cardinality of Gamma^hat(x)' as implied by the statement of this theorem.]

Fillable Holes in the proof of Corollary 1: from G to G' and back again. How can we make a statement about the graph G' when all we are talking about is about the subgraph induced by Gamma^hat(x0). Also, when and how are theorem 2, theorem 1 used? At what particular locations? How is the result for G' extensikble to G? remember, we are talking about two graphs here, G and G'. Also about two theorems 1 and 2. The statement of corollary 1, from the outside is more general, but needs to be taken care of.

Proof by contradiction: If