Extremal Choices¶
In previous chapters, we saw how problems can be easily proven by choosing something that has the property of being the largest or smallest. For example, the longest path is a common extremal choice whose properties help us in solving problems. In this section, we will become familiar with other extremal choices.
Every extremal choice has properties that can help us in solving problems. In the following, we will only mention the properties, and the proof of these properties (which is generally simple) is left to the reader.
Shortest Path Between Two Vertices¶
Properties¶
No vertex outside this path has an edge to two vertices on this path that are 3 edges or more apart.
As a result of the above statement, every vertex from outside has an edge to at most 3 vertices within this path.
The subgraph induced by the vertices of this path is the path itself, and there are no other edges in it.
Longest Path in a Graph¶
Properties¶
All vertices adjacent to the start and end vertices of this path are within this path.
No two consecutive vertices have common neighbors outside the path.
If the ends of this path are connected, this path contains all vertices of its component.
Smallest Cycle¶
Properties¶
The subgraph induced by the vertices of this cycle is the cycle itself, and there are no other edges in it.
If the length of this cycle is greater than 4, every vertex from outside this cycle has an edge to at most one vertex of this cycle.
Smallest Odd Cycle¶
Properties¶
The subgraph induced by the vertices of this cycle is the cycle itself, and there are no other edges in it.
If the length of this cycle is greater than three, every vertex from outside this cycle has an edge to at most two vertices of this cycle.
Lowest Leaf in a Rooted Tree¶
Refers to a leaf of the tree that has the greatest height.
Properties¶
All children of the parent of this leaf are leaves.
This book is made by The Shaazzz contributors.
It is publicly available with cc-by-sa license.
Last updated at اکتبر 13, 2025.
Rendered by Sphinx (4.3.2) and Minoo theme (Beta 0.9.7).
