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

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.

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.

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

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 python3importitertoolsdefcomponent_sizes(G):"""component sizes in an undirected graph"""comps=list(set([v])forvinG[0])foreinG[1]:s,t=e[0],e[1]idx_s,idx_t=-1,-1fori,compinenumerate(comps):ifsincomp:idx_s=iiftincomp:idx_t=iifidx_s==idx_t:continueelse:foritemincomps[idx_t]:comps[idx_s].add(item)comps.remove(comps[idx_t])returntuple(sorted(len(comp)forcompincomps))assertcomponent_sizes(([1],[]))==(1,)assertcomponent_sizes(([1,2],[]))==(1,1)assertcomponent_sizes(([1,2],[(1,2)]))==(2,)assertcomponent_sizes(([1,2,3],[(1,2)]))==(1,2)defsubgraph(G,excl_vs):"""Subgraph induces by excluding vertices"""red_V=tuple(filter(lambdav:vnotinexcl_vs,G[0]))red_E=tuple(filter(lambdae:e[0]notinexcl_vsande[1]notinexcl_vs,G[1]))return(red_V,red_E)assertsubgraph(([1],[]),[1])==(tuple(),tuple())assertsubgraph(([1,2],[(1,2)]),[1])==((2,),tuple())assertsubgraph(([1,2,3],[(1,2),(2,3),(3,1)]),[1])==((2,3),((2,3),))if__name__=='__main__':defexcl_vs_selection(G):forsizeinrange(len(G[0])):forselinitertools.combinations(G[0],r=size):yieldset(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=K5forexcl_vsinexcl_vs_selection(G):sub=subgraph(G,excl_vs)sizes=component_sizes(sub)odd_sized_comps=len(list(map(lambdav:v%2==0,sizes)))ifodd_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.

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:

importitertoolsdefparenthesized(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)defmain():"""Main routine generating math expressions equating 24 using numbers {1, 3, 4, 6} exactly once and using operators -, +, / or *. """forarrinitertools.permutations([1,3,4,6]):forexprinparenthesized(*arr):# we can omit '-' in these iterations, because all values# will also be considered with a signforfo,so,toinitertools.product(['+','/','*'],repeat=3):fors1,s2,s3,s4initertools.product(['','-'],repeat=4):try:# replace operatorse=expr.replace('$',fo).replace('@',so).replace('!',to)# use either sign '' (hence +) or '-' (hence -) at every placee=e.replace('`',s1).replace('<',s2).replace('>',s3).replace('_',s4)result=eval(e)exceptZeroDivisionError:continueifresult==24:yieldeif__name__=='__main__':forsolution_expressioninmain():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:

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.

Factor 6? So we look for factor 4 as well, right? Actually no. I mean yes, but with an indirect representation.

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.

How about 1 / (1 / 4)? Two ones? I guess one of them has to be 6.

Given 6 / (1 / 4)? How can we represent 1/4 using {1, 3, 4}?

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.

First, we generate the documentation.

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.)

Three files are generated, namely commafree-eastman.idx, commafree-eastman.scn and commafree-eastman.tex.

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:

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.

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.

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.

We generate the source code:

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.)

Nice! So we got a commafree-eastman.c file.

We compile the C file with a C compile like the GCC:

./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]
}
^

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.