A question in an oriented connected graph.

Question

In an oriented connected graph, I knew E-V+1 is called the number of circuits. I have a feeling that it may be related to the number of "independent" loop(a path from a vertex to itself). But could it be shown concretely?

Answer 1

In topology, one studies the "1st cycle group" of a graph $G$, denoted $C_1(G)$. Although referred to as a group, one can think of it as a vector space. The number $1+E-V$ is the dimension of this vector space.

It is not quite accurate, as the answer of @farhbach shows, to call $E-V+1$ the "number of circuits". It would be better to call it the "maximum number of linearly independent cycles". In the example of @fahrbach, any two of the three cycles that he mentions are linearly independent, but the three of them together are not linearly independent.

One can define $C_1(G)$ rigorously with linear algebra, but I'll give an intuitive explanation, using the answer of @fahrbach as an example. First, choose orientations of the edges of $G$. For the example, there are five edges $AB$, $AC$, $AD$, $BD$, $CD$ where for example $AB$ is oriented to have initial vertex $A$ and terminal vertex $B$. A "chain" on the graph $G$ is an assignment of real numbers to the edges. One might think of a chain as measuring some kind of "rate of flow" of some physical substance. A chain is a "cycle" if at each vertex the total inflow equals the total outflow. Cycles form a vector space, which in topology is denoted $C_1(G)$.

For instance, $$AB+BD-AD = 1 \cdot AB + 1 \cdot BD - 1 \cdot DA $$ is a cycle, because at the vertex $A$ the edge $+AB$ contributes an outflow of $1$ which is balanced by the inflow of $1$ created by the edge $-AD$. Similarly at $B$ and $D$ which have a balanced inflow of $1$ and outflow of $1$. At $C$ the inflow and outflow are both zero. So the total inflow and outflow at each vertex of zero, which makes $AB+BD-AD$ a cycle.

Cycles can have any real coefficients, so for example $$AB + BD - 2AD + AC + CD = (AB+BD-AD) + (AC+CD-AD) $$ is also a cycle.

So the answer to your question is that $E+V-1$ is the rank of $C_1(G)$, meaning the size of a "basis" meaning a maximal, linearly independent set of cycles. In the example, $AB+BD-AD$ and $AC+CD-AD$ form a basis of size $E+V-1=2$.

Answer 2

This doesn't seem to be the case. Consider the following graph $G$:

A - - - B
| \     |
|   \   |
|     \ |
C - - - D

There are $5$ edges and $4$ vertices, so the number of circuits is $E-V+1=5-4+1=2$. Note though that there are $3$ circuits containing A: ABDA, ACDA, and ABDCA. It must be counting something else or nothing at all.