What is a 1-graphic matroid?

Question

I came across the definition of a 1-graphic matroid as follows:

The 1-graphic matroid: the set of edges that form a forest with at most one simple cycle.

Isn't a forest supposed to have no cycles? What does the above definition mean?

Edit: This is from a paper on Rewards for Travelling Salesman Problem. It is the last point (iii) that confuses me.

Given a complete graph, the classical Traveling Salesman Problem (TSP) is to find a minimum cost tour. The TSP can be divided into two variants: the Asymmetric TSP and the Symmetric TSP. In the ATSP, for two vertices u and v, the cost of edge $(u, v)$ is different from the cost of $(v, u)$, which amounts to the graph being directed. In the STSP, $c(u, v) = c(v, u)$, which is the case if the graph in undirected.

In order to formulate the TSP, the set of possible solutions can be defined using an independence system. The base set of the system is the set of edges in the complete graph. For the ATSP, a set of edges is independent if they form a collection of vertex disjoint paths, or a complete Hamiltonian cycle.

The ATSP can be formulated as the intersection of 3 matroids. These are: (i) Partition matroid: Edge sets such that the in-degree of each vertex ≤ 1
(ii) Partition matroid: Edge sets such that the out-degree of each vertex ≤ 1
(iii) The 1-graphic matroid: the set of edges that form a forest with at most one simple cycle.

Answer 1

This is a slightly unusual way to formulate the ATSP as the intersection of three matroids. Let me first give you the usual way, which may help clarify things.

(A source for this is Chapter 8 of Combinatorial Optimization: Networks and Matroids by Eugene Lawler.)

First suppose we are looking for an open tour that starts at node $1$, ends at node $n$, and visits all other nodes. We assume there are no edges into node $1$ or out of node $n$. Such tours are exactly the maximal ($(n-1)$-edge) elements of the intersection of the following three matroids:

1. The partition matroid whose independent sets are all the edge sets with at most $1$ edge into every node. (It's a partition matroid because we partition the edge set according to the target vertex of an edge, and the independent sets pick at most one edge from every part of the partition.)
2. The partition matroid whose independent sets are all the edge sets with at most $1$ edge out of every node.
3. The graphic matroid of the underlying undirected graph. This is a standard definition: the independent sets of this matroid are all the forests in the graph (so the maximal independent sets are the spanning trees).

If we want a closed tour, we can reduce it to the version above as follows. Split node $1$ of an $n$-node graph into nodes $1'$ and $n+1$, where node $1'$ keeps all the outgoing edges of node $1$, and node $n+1$ keeps all the incoming edges. Then, find open tours from $1'$ to $n+1$.

Of course, there is a bijection between the edges of the $n+1$-node graph we found, and the $n$-node graph we started with, so there is also a correspondence between edge sets in the $n+1$-node graph and the $n$-node graph. So we could define three matroids for a closed tour directly:

1. The definitions of the partition matroids remain the same.
2. Both of them.
3. The matroid corresponding to the graphic matroid now has the following independent sets: subgraphs which are either acyclic or contain a unique cycle through node $1$.

---

I assume that your slightly nonstandard definition has, as its matroid in (iii), all subgraphs which are either acyclic or contain any one cycle. (We are still looking at the undirected graph here.) These subgraphs are of course not all forests, but you can see how the confusion arises, because they are inspired by a situation where they were all forests.