#7 Graphs II

In the sum of degrees, each edge is counted exactly twice: once at each endpoint. Therefore the sum of degrees is \(2m\).

The sum of degrees is \(2m\), so it is even. The sum of degrees of even-degree vertices is even. Hence the sum of degrees of odd-degree vertices is also even. A sum of odd integers is even only when the number of summands is even.

Choose a longest simple path in the tree. If an endpoint has a neighbour outside the path, the path can be extended. If it is adjacent to another vertex of the path besides its neighbour on the path, a cycle appears. Hence its degree is \(1\). The same holds for the other endpoint. Thus there are two leaves.

Every connected graph has a spanning tree. A spanning tree contains all \(n\) vertices and has exactly \(n-1\) edges. The original graph contains all edges of this tree and possibly more. Hence it has at least \(n-1\) edges.

Let the new edge join vertices \(u\) and \(v\). In the tree, there was exactly one simple path between \(u\) and \(v\). This path together with the new edge forms a cycle.

No other cycle can appear: any cycle after the addition must use the new edge, because there were no cycles before. Then the rest of that cycle would be another path between \(u\) and \(v\) in the tree, impossible.

Let the components have \(n_1,n_2,\ldots,n_c\) vertices. Each component is a tree, so it has \(n_i-1\) edges. The total number of edges is

\[\sum_{i=1}^c(n_i-1)=\sum_{i=1}^c n_i-c=n-c.\]

Let the removed edge join \(u\) and \(v\). Since it lies on a cycle, after removing it, the rest of the cycle still contains a path from \(u\) to \(v\).

Any path in the original graph that used edge \(uv\) can be modified: replace \(uv\) by this alternate path. Hence connectedness is preserved.

Suppose the graph contains a cycle. Remove one edge of this cycle; connectedness remains. Then we obtain a connected graph on \(n\) vertices with \(n-2\) edges.

But a connected graph on \(n\) vertices has at least \(n-1\) edges. Contradiction. Hence there are no cycles, and the graph is a tree.

Take a spanning tree of the graph. It has \(n-1\) edges, so the original graph has exactly one edge outside this spanning tree. Adding one edge to a tree creates exactly one cycle.

Every cycle of the original graph must use this single extra edge, because the tree itself has no cycles. Therefore there is exactly one cycle.

Let the graph be split into parts \(A\) and \(B\), and every edge joins a vertex of \(A\) to a vertex of \(B\). Moving along a cycle, the vertices alternate between \(A\) and \(B\). After an odd number of steps, we would be in the other part, but to close the cycle we must return to the starting vertex and starting part. Hence the cycle length is even.

Colour vertices at even distance from \(v\) into one part and vertices at odd distance into the other. We need to prove that no edge joins vertices in the same part.

Suppose an edge \(xy\) joins two vertices with the same distance parity. Take shortest paths from \(v\) to \(x\) and from \(v\) to \(y\). These paths have a common initial segment; after removing it, the remaining two paths have total even length. Adding edge \(xy\) gives an odd cycle. This is forbidden. Hence every edge joins different parts.

If the trail is not closed, then at every internal vertex the used edges are paired: enter and leave. Thus internal vertices have even degree. Only the start and end may have odd degree.

If the trail is closed, then at the starting vertex entrances and exits also pair up, so all degrees are even. Hence the number of odd-degree vertices is either \(0\) or \(2\).

Let \(x\) be a leaf and \(y\) its only neighbour. In a perfect matching, vertex \(x\) must be covered by some edge. The only edge incident to \(x\) is \(xy\). Therefore edge \(xy\) must belong to the matching.

Suppose there is an edge \(uv\) whose two endpoints are not endpoints of chosen matching edges. Then \(uv\) is disjoint from every edge of the matching, so it can be added. This contradicts maximality by inclusion.

Hence every edge has at least one endpoint among the endpoints of chosen edges.

Every edge has one endpoint in \(A\) and one endpoint in \(B\). Counting edges by vertices of \(A\), we get \(d|A|\). Counting by vertices of \(B\), we get \(d|B|\). These are the same number of edges, so \(d|A|=d|B|\). Since \(d>0\), we have \(|A|=|B|\).

Start at any vertex and follow unused edges as long as possible. Since all degrees are even, one cannot get stuck at a vertex different from the start: every entrance requires another exit. Thus we obtain a closed walk.

Choose a closed walk using as many edges as possible. If it does not use all edges, connectedness gives a vertex of the walk incident to an unused edge leading into the unused part. Starting there and moving along unused edges, we again obtain a closed walk, which can be spliced into the first one. This increases the number of used edges, a contradiction.

Therefore the maximal walk uses all edges.

Let \(f\) be the number of faces. By Euler's formula, \(n-m+f=2\). Since the graph is simple and \(n\ge3\), every face is bounded by at least three edges. In the sum of face boundary lengths, every edge is counted twice, so \(3f\le2m\).

Thus \(f\le\frac{2m}{3}\), and \(2=n-m+f\le n-m+\frac{2m}{3}=n-\frac{m}{3}\). Hence \(m\le3n-6\).

Necessity follows from entry-exit pairs: only the start and end of a non-closed Euler trail may be odd, while an Euler circuit has no odd vertices.

For sufficiency, if there are no odd vertices, the lemma on even degrees in a connected graph gives an Euler circuit.

If there are exactly two odd vertices, call them \(a\) and \(b\). Add a new edge \(ab\). Now all degrees are even, so the new graph has an Euler circuit. Remove the added edge from this circuit. The remaining sequence of edges is an Euler trail of the original graph from \(a\) to \(b\).

Let \(f\) be the number of faces. By Euler's formula, \(n-m+f=2\). A bipartite graph has no odd cycles, in particular no triangles. Therefore every face boundary has length at least \(4\).

The sum of face boundary lengths is \(2m\), so \(4f\le2m\), i.e. \(f\le\frac{m}{2}\). Then \(2=n-m+f\le n-m+\frac{m}{2}=n-\frac{m}{2}\). Hence \(m\le2n-4\).

A tree has no cycles, hence no odd cycles. Therefore it is bipartite: its vertices can be split into two parts \(A\) and \(B\), with every edge going between the parts.

Inside each part there are no edges, so each part is an independent set. Of the two numbers \(|A|\) and \(|B|\), whose sum is \(n\), one is at least \(\lceil n/2\rceil\). This larger part gives the desired independent set.