Question

Let \(G\) be a tree with all vertices having odd degree. Prove that \(G\) contains an odd number of edges. Show that this is not true if \(G\) is not a tree.

Short answer

In a tree, the sum of odd vertex degrees means an odd number of edges. Not true for non-trees.

Step-by-step solution

Understanding the Tree and its Properties

A tree is a connected graph with no cycles. In a tree with vertices all of odd degree, consider that a tree with \(n\) vertices has exactly \(n-1\) edges. We must show that \(n-1\) is odd.

Use the Handshaking Lemma

The Handshaking Lemma states that the sum of the degrees of all the vertices in a graph is equal to twice the number of edges: \( \text{Sum of degrees} = 2e \). For a tree, since all degrees are odd, the sum of degrees is odd.

Odd Sum Implies Odd Number of Vertices

With degrees being odd and their sum being odd (since the sum \(d_1 + d_2 + \, ... \, + d_n\) where all \(d_i\) are odd is odd), \(n\) itself must be odd because an odd number of odd numbers sum to an odd number. Let \(n = 2k + 1\), where \(k\) is an integer.

Conclude with Number of Edges in a Tree

Since the number of edges \(e = n - 1\) and we have \(n = 2k + 1\), then: \[ e = 2k + 1 - 1 = 2k, \] which is odd. This proves that the number of edges in \(G\) is odd. (Correct adjustment mistake: \( e = n - 1 = 2k\).)

Consider if the Graph is not a Tree

If \(G\) is not a tree, it may contain cycles, and it is possible for the degrees to sum up to an even number of edges. Thus, without the tree structure, having all vertices of odd degrees does not ensure an odd number of edges.

Key concepts

Odd Degree

In the realm of graph theory, the degree of a vertex refers to the number of edges connected to it. A vertex with an odd degree has an odd number of edges attached. In the context of trees, which are graphs with no cycles and always remain connected, having all vertices with odd degrees leads to interesting properties when considering the number of edges. Each vertex in a tree having an odd degree means the sum of all vertex degrees must also be an odd number. This arises due to the properties of odd numbers: when you add two odd numbers, you get an even number, but an odd total indicates an odd count of odd numbers.

Handshaking Lemma

The Handshaking Lemma is a fundamental principle in graph theory which states that the sum of the degrees of all the vertices in a graph equals twice the number of its edges. Represented mathematically as: \( \text{Sum of degrees} = 2 \times \text{number of edges} \). This is analogous to the literal example of people shaking hands, where each handshake involves two people (or vertices), mirroring how each edge in a graph connects two vertices. In a tree where every vertex has an odd degree, the sum of degrees is odd, conflicting with the Handshaking Lemma's usual condition of being twice a whole number, highlighting the odd count of edges in such unique tree structures.

Connected Graph

A connected graph implies every vertex is accessible from any other vertex, forming a single piece. Trees are the quintessential examples of connected graphs, as they possess no cycles and link every vertex with a unique path. In a connected graph like a tree, each component is intricately linked to sustain its non-cyclic, unbroken nature, and even if all vertices have odd degrees, the graph remains connected. Notably, unlike generic graphs which can break into disconnected parts or cycles when vertices have odd degrees, trees compensate with their acyclic structure to maintain connectivity and thus adhere to their inherent properties, like tree edge count being one less than the number of vertices.

Cycles in Graphs

Cycles in graphs occur when a path through the graph returns to the starting vertex without retracing any edge. Trees, by nature, do not contain cycles, distinguishing them sharply from general graphs. When cycles appear, the structure of the graph changes fundamentally, often impacting properties such as vertex degrees and connectivity. A graph with vertices all of odd degree without ensuring the tree property can form cycles, and as cycles emerge, the conditions for having an odd number of edges may no longer apply. This occurs because cycles allow for varying lengths and path returns, potentially increasing or altering the evenness of the summed degrees, diverging from strict tree constraints.