When is Tutte’s theorem in K₅ violated?

Theorem

A graph, G = (V, E), has a perfect matching if and only if for every subset U of V, the subgraph induced by V − U has at most |U| connected components with an odd number of vertices.
Tutte’s theorem

Illustration
tutte_theorem_examples
Figure 1. Tutte theorem examples

Consider the two examples given in Figure 1. G is a bipartite graph and we consider two possible subsets U the induced subgraph of G-U is given on the right side.

  1. For U₁ the number of odd components in G-U is 1 and the size of U is given with 3. Because 1 ≤ 3, the Tutte theorem holds.
  2. For U₂ the number of odd components in G-U is also 1 and the size of U is also given with 3. Again, the Tutte theorem holds.

For any U, this condition will hold. Underneath the perfect matching is given (vertex 1 is associated to vertex 2, etc).

Problem setting

planar graph K5

Figure 2. Planar graph K5 and a reduced variant

Consider graph K₅. A perfect matching clearly cannot exist for K₅, because a perfect matching can only exist if the number of vertices is even (as every vertex is associated to another vertex). Because the Tutte theorem provides a necessary and sufficient condition for the existence of a perfect matching, it should yield

For some subset U of V, the subgraph induced by V − U
has less than |U| connected components with an odd number of vertices.

Question

What is U for K₅? The solution is equivalent for its incomplete variant, which was originally given to me.

Solution

I wasn’t able to come up with a solution. So I wrote a program to try all combinations:

#!/usr/bin/env python3

import itertools

def component_sizes(G):
    """component sizes in an undirected graph"""
    comps = list(set([v]) for v in G[0])
    for e in G[1]:
        s, t = e[0], e[1]
        idx_s, idx_t = -1, -1
        for i, comp in enumerate(comps):
            if s in comp:
                idx_s = i
            if t in comp:
                idx_t = i
        if idx_s == idx_t:
            continue
        else:
            for item in comps[idx_t]:
                comps[idx_s].add(item)
            comps.remove(comps[idx_t])
    return tuple(sorted(len(comp) for comp in comps))

assert component_sizes(([1], [])) == (1,)
assert component_sizes(([1, 2], [])) == (1, 1)
assert component_sizes(([1, 2], [(1, 2)])) == (2,)
assert component_sizes(([1, 2, 3], [(1, 2)])) == (1, 2)

def subgraph(G, excl_vs):
    """Subgraph induces by excluding vertices"""
    red_V = tuple(filter(lambda v: v not in excl_vs, G[0]))
    red_E = tuple(filter(lambda e: e[0] not in excl_vs and e[1] not in excl_vs, G[1]))
    return (red_V, red_E)

assert subgraph(([1], []), [1]) == (tuple(), tuple())
assert subgraph(([1, 2], [(1, 2)]), [1]) == ((2,), tuple())
assert subgraph(([1, 2, 3], [(1, 2), (2, 3), (3, 1)]), [1]) == ((2, 3), ((2, 3),))

if __name__ == '__main__':
    def excl_vs_selection(G):
        for size in range(len(G[0])):
            for sel in itertools.combinations(G[0], r=size):
                yield set(sel)

    K5 = ((1, 2, 3, 4, 5), list(itertools.combinations(range(1,6), r=2)))
    reduced_K5 = ((1, 2, 3, 4, 5), [(1, 2), (2, 3), (3, 4), (4, 5), (5, 1)])

    G = K5
    for excl_vs in excl_vs_selection(G):
        sub = subgraph(G, excl_vs)
        sizes = component_sizes(sub)
        odd_sized_comps = len(list(map(lambda v: v % 2 == 0, sizes)))
        if odd_sized_comps > len(excl_vs):
            print(excl_vs)
            #raise ValueError("Tutte theorem violated with exclusion vertices {}".format(excl_vs))

The program yields set(). Hence the only solution is the empty set.

Consider U = {}. Then the induced graph is K₅ itself. The number of connected components in K₅ is 1 (all pairs of vertices are reachable from each other) and this component has an odd number of vertices (namely 5). The size of U is 0. And 1 > 0, so the Tutte theorem is violated and no perfect matching exists indeed.

When is Tutte’s theorem in K₅ violated?

Make 24 out of 1, 3, 4 and 6

Problem

Give a mathematical expression which equals 24. This expression is only allowed to use the basic arithmetic operators +, -, * and /. The numbers 1, 3, 4 and 6 must occur exactly once. No magic or tricks!

Setting

I was given this problem last Friday by one colleague. It was ridiculously difficult to come up with a solution. As mathematician you try to understand the structure behind the problem. You look at the prime numbers involved. In the expression you have {3, 2, 2, 2, 3} and in 24 you have {2, 2, 2, 3}. So you need to get rid of one three. But how? None of us 6 guys came up with a solution in less than an hour. But we actually found one academic who found the solution after 2 hours (a bit of sleep was involved, because he was very tired).

Well, my mathematical brain failed, but my computer science brain screamed “brute force!”. So let’s do it. I wrote a python script, which solved a subproblem in 18 lines. This is a more complete version which solves the problem for any four numbers and any target value. This script prints possible correct solutions to stdout in less than 0.5 seconds:

import itertools

def parenthesized(a, b, c, d):
    """Generate all expressions where operators
    are represented with substitution characters
    """
    yield '((`{} $ <{}) @ (>{} ! _{}))'.format(a, b, c, d)
    yield '((`{} $ (<{} @ >{})) ! _{})'.format(a, b, c, d)
    yield '(`{} $ ((<{} @ >{}) ! _{}))'.format(a, b, c, d)
    yield '(`{} $ (<{} @ (>{} ! _{})))'.format(a, b, c, d)

def main():
    """Main routine generating math expressions equating 24
    using numbers {1, 3, 4, 6} exactly once and using operators
    -, +, / or *.
    """
    for arr in itertools.permutations([1, 3, 4, 6]):
        for expr in parenthesized(*arr):
            # we can omit '-' in these iterations, because all values
            # will also be considered with a sign
            for fo, so, to in itertools.product(['+', '/', '*'], repeat=3):
                for s1, s2, s3, s4 in itertools.product(['', '-'], repeat=4):
                    try:
                        # replace operators
                        e = expr.replace('$', fo).replace('@', so).replace('!', to)
                        # use either sign '' (hence +) or '-' (hence -) at every place
                        e = e.replace('`', s1).replace('<', s2).replace('>', s3).replace('_', s4)
                        result = eval(e)
                    except ZeroDivisionError:
                        continue
                    if result == 24:
                        yield e

if __name__ == '__main__':
    for solution_expression in main():
        print(solution_expression)
Spoiler

In the following I will give a list of hints. The further below you go, the closer you come to the solution (select text to display items). The solution itself is not given here:

  1. Most values we ended up with are too small for 24. So we conjectured that number 6 will occur as factor, which turned out to be true.
  2. Factor 6? So we look for factor 4 as well, right? Actually no. I mean yes, but with an indirect representation.
  3. Given {1, 4} on the left-hand side and {1, 3, 4} on the right-hand side. Find operators such that LHS and RHS equate.
  4. How about 1 / (1 / 4)? Two ones? I guess one of them has to be 6.
  5. Given 6 / (1 / 4)? How can we represent 1/4 using {1, 3, 4}?
Make 24 out of 1, 3, 4 and 6

Running Donald Knuth’s CWEB programs

I just realized that no-one documented how to quickly run Donald Knuth’s programs he publishes in his WEB system.

Suppose you want to compile a program like commafree; a program he wrote between September and December 2015 for his Annual Christmas tree lecture in 2015 about Universal Commafree Codes.

  1. Download the webfile which comprises documentation and source code.

    wget http://www-cs-faculty.stanford.edu/~uno/programs/commafree-eastman.w
  2. Recognize that the programming language used is C. Hence we need to use cweave and ctangle; not the original weave and tangle designed for Pascal.
    All those programs come bundled with TeX distributions like TeXLive. Once you have them installed and your system can find executables like pdflatex, it will also find cweave, etc.
  3. First, we generate the documentation.
    1. We run

      cweave commafree-eastman.w

      On my system this gives the output

      This is CWEAVE, Version 3.64 (TeX Live 2015/dev/Debian)
      *1*3*8
      Writing the output file...*1*3*8
      Writing the index...
      Done.
      (No errors were found.)
    2. Three files are generated, namely commafree-eastman.idx, commafree-eastman.scn and commafree-eastman.tex.
    3. As a small remark, the TeX file uses the cwebmac definitions. So it is a file full of definitions and this file is also provided with your TeX distribution:
      % head -n 1 commafree-eastman.tex
      \input cwebmac
      % locate cwebmac
      /usr/share/texlive/texmf-dist/tex/plain/cweb/cwebmac.tex
      /usr/share/texlive/texmf-dist/tex/plain/cweb/pdfXcwebmac.tex
      /usr/share/texlive/texmf-dist/tex/plain/cweb/pdfcwebmac.tex
      /usr/share/texlive/texmf-dist/tex/plain/cweb/pdfdcwebmac.tex
      /usr/share/texlive/texmf-dist/tex/plain/cweb/pdffcwebmac.tex
      /usr/share/texlive/texmf-dist/tex/plain/cweb/pdficwebmac.tex
    4. Then we run the original tex program to build a dvi file.

      tex commafree-eastman.tex

      This gives me the output:

      This is TeX, Version 3.14159265 (TeX Live 2015/dev/Debian) (preloaded format=tex)
      (./commafree-eastman.tex
      (/usr/share/texlive/texmf-dist/tex/plain/cweb/cwebmac.tex) *1 [1] *3 [2]
      [3] *8 Index: (./commafree-eastman.idx) [4] Section names:
      (./commafree-eastman.scn) [5] Table of contents: (./commafree-eastman.toc)
      [0] )
      Output written on commafree-eastman.dvi (6 pages, 16116 bytes).
      Transcript written on commafree-eastman.log.
    5. Followingly, a file commafree-eastman.dvi is written as the output states. Opening it directly with evince 3.14.2 shows the output with some errors (the typical font encoding problems of TeX like < in #include statements is replaced by ¡). With okular 0.21.3 I can view the document without any problems.
    6. We convert the DVI file using the utility dvipdfm provided with your TeX distribution:
      dvipdfm commafree-eastman.dvi

      For me, this gives:

      commafree-eastman.dvi -> commafree-eastman.pdf
      [1][2][3][4][5][6]
      45807 bytes written

      Then we have a PDF output file commafree-eastman.pdf containing the documentation.
      I think this is the usual way to view documents, you were looking for.

  4. We generate the source code:

    1. First we run ctangle:
      ctangle commafree-eastman.w

      which gives me:

      This is CTANGLE, Version 3.64 (TeX Live 2015/dev/Debian)
      *1*3*8
      Writing the output file (commafree-eastman.c):
      Done.
      (No errors were found.)
    2. Nice! So we got a commafree-eastman.c file.
    3. We compile the C file with a C compile like the GCC:
      gcc -Wall -o commafree-eastman commafree-eastman.c

      This gives me:

      ./commafree-eastman.w:38:1: warning: return type defaults to ‘int’ [-Wreturn-type]
       main (int argc,char*argv[]) {
       ^
      ./commafree-eastman.w: In function ‘main’:
      ./commafree-eastman.w:42:1: warning: control reaches end of non-void function [-Wreturn-type]
       }
       ^
    4. We run this new executable program:
      ./commafree-eastman
      Usage: ./commafree-eastman x1 x2 ... xn

      This gives the same output as in the video.

So we got a commafree-eastman.pdf and commafree-eastman.c file which was what we were going for.
I will also refer here to my Literate programming talk at PyGraz back then.

Running Donald Knuth’s CWEB programs