Interpretation of a claim in graph theory

63 Views Asked by At

Theorem For a connected nontrivial graph with exactly $2k$ odd vertices, the minimum number of trails that decompose it is $\max\{k,1\}$.

For me the formulation of the claim leaves room to two interpretations

  1. There are $2k$ odd vertices; exactly means "no even vertex"
  2. There are $2k$ odd vertices and zero or more even vertex; exactly means "$2k$ odd vertices and no one more"

Is the claim vague or is my English understanding vague?

1

There are 1 best solutions below

2
On

It means the latter, any number of vertices of even degree are permitted.

Compare/contrast: "My head contains exactly two eyes." The word "exactly" is modifying "two", not "contains". One way to see this is to delete modifiers to see what meaning (if any) survives.

  • "My head contains two eyes." True. Of course, if my head contained four eyes, this statement is still true. "Exactly" must be a leaf in the dependency graph of the sentence.
  • "My head contains exactly eyes." Mangled. There may exist a context where a distinction between approximate eyes and exact eyes is meaningful, but I don't know of one.

Compare/contrast: "My bag exactly contains two books." "Exactly" now modifies "contains" and informs the reader that there are zero non-books and two books in the bag.