Exploring Connected Planar Graphs with Odd-Degree Vertices

In graph theory, a connected planar graph can indeed have vertices with odd degrees but the number of vertices with odd degree in any graph is always even. This is a consequence of the Handshaking Lemma, which states that the sum of the degrees of all vertices in a graph is twice the number of edges. Since edges connect two vertices, each edge contributes an even degree to the total degree count. Therefore, if you have a graph with odd-degree vertices, they must exist in pairs to maintain the evenness of the total degree sum. A connected planar graph can have two odd vertices but cannot have just one or any other odd number of odd vertices. In summary, the presence of two odd vertices is possible but they must exist in pairs (2, 4, 6, etc.).

Examples of Connected Planar Graphs with Odd-Degree Vertices

Indeed, you can find examples of such things being connected planar graphs. Below are three examples demonstrating this:

A simple tree with a single edge, a minimal example of a connected planar graph with two odd-degree vertices. A box plus an edge, another example of a connected planar graph with two odd-degree vertices. An outerplanar graph where the two vertices with odd degree form a chord, showcasing that such graphs can be more complex and diverse.

A Remark: It is possible to have connected planar graphs with many odd-degree vertices, and the "2" is not special. We can create as many odd-degree vertices as we want by using star graphs. Consider the star graph shown below, which is planar and connected. By fixing the number of vertices, the tips of the star graph always have degree 1. The parity of the middle vertex of the star depends on the number of vertices. The number of vertices of odd degree is at least one less than the number of vertices. An interesting fact is that if the number of vertices in this graph is even, then the graph collapses into a generalization of the first example I presented, where all vertices have odd degree; but when the number of vertices is odd, every vertex except the middle one (which is even) has an odd number of vertices. This odd observation is no coincidence, as the number of odd-degree vertices in any graph is even, and this falls out of the Handshaking Lemma.

This odd observation is no coincidence! The number of odd-degree vertices in any graph is even, which is a direct result of the Handshaking Lemma. For more discussion, see the following references:

Reference 1 Reference 2 Reference 3

Indeed, if you are not happy that the star graph is a tree and still want an example with the same property, you can include a path along the tips to form a wheel graph. All the tips will now have degree 3 instead of 1! This construction provides a more robust example while maintaining the property of odd-degree vertices.

I hope this helps!