# Tag Info

213

First you have to draw the petals. There are $4!=24$ ways to choose the order of the petals and $2^4=16$ ways to choose the direction you go around each petal. Then you go down the stem to the leaves. There are $2! \cdot 2^2=8$ ways to draw the leaves. Finally you draw the lower stem. $24 \cdot 16 \cdot 8=3072$

120

At the beginning you could go 8 different ways, then you could go 6 different ways, then you could go 4 and 2 different ways but in the down of the picture you could go at first 4 different ways and 2 at the end. $8\cdot6\cdot4\cdot2\cdot4\cdot2 = 3072$

118

Starting at the top, going clockwise: center: 1, 2, 3 middle: 2,4,3,4,2,4 outside: 1 I hope this helps $\ddot\smile$

105

If everyone knows everyone, then you are done. Otherwise choose two people, A and B say, who don't know each other. These two people are part of $23$ triples. In each of these triples, either A knows the third person, or B knows the third person. Thus one of A or B knows (at least) $12$ people.

95

I'll try to answer. It's a rather difficult question since (1) answering why something in mathematics is the way it is is troublesome; and (2) this subject has technical details that make it difficult to give a "layman's explanation". It appears that you have watched David Metzler's videos on fast-growing functions, so you know a little about ordinals, and ...

90

All of these are sequences of vertices and edges. They have the following properties : Walk    : Vertices may repeat. Edges may repeat (Closed or Open) Trail     : Vertices may repeat. Edges cannot repeat (Open) Circuit : Vertices may repeat. Edges cannot repeat (Closed) Path     : ...

82

Once you have an isomorphism, you can create an animation illustrating how to morph one graph into the other. Let's say that ${vc}_1$ is a list of vertex coordinates for one and ${vc}_2$ is the corresponding list of vertex coordinates for the other. (It's important that the order of the vertex coordinates be dictated by the isomorphism.) We can then morph ...

81

Cookie Monster is facing four jars of cookies with seven trails of cookie crumbs between them. Obviously, Cookie Monster does not want to go from jar to jar without also eating the trails of crumbs between them.

73

Please help me hand out these blank pieces of paper and some crayons. Now look at this weird picture: Can any of you draw a copy of this picture without lifting your crayon off the paper, and also not tracing the same line twice?

70

No, not even if we permit non-regular hexagonal faces. (We do, however, preclude hexagons that are not strictly convex—where interior angles can be $180$ degrees or more—since those permit degenerate tilings of the sort David K mentions in the comments.) The reason is more graph-theoretical than geometrical. We begin with Euler's formula, relating the ...

68

First of all, let me state my preconditions. Since you write that there are three graphs with two edges on three vertices it seems you are talking about the labelled case, which is what I will work with from now on. As this is truly a vast field of investigation I will just show you how to calculate these numbers (connected graphs on $n$ nodes having $k$ ...

68

It is possible, and it's actually quite easy. Start on the red dot and move your pen according to numbers in a picture below.

57

A more general approach to this is given by topological sorting. In particular, a topological sort exists if and only if the graph is a directed acyclic graph. The 'algorithms' described in the other answers effectively perform a topological sort, in that they repeatedly remove vertices with no incoming/outgoing edges. For instance, a topological ordering ...

53

Although the question has already been thoroughly answered, here is an unusual approach to checking if a graph is planar that I'm very fond of which works well here. First, we notice that there's a cycle passing through all $12$ vertices: (This method is only guaranteed to settle the question one way or the other if we find such a cycle, though for a cycle ...

51

You can't have an odd number of cats, not because of geometry, but something more fundamental: the handshaking lemma. Basically, if two cats seeing each other is mutual, then the number of cats that see an odd number of other cats must be even.

51

Step 1. Since $A$ has no indegree it can't be part of any cycle. So remove it. We have now graph $G_1$. Step 2. Since $C$ has no indegree it can't be part of any cycle (in this new graph $G_1$). So remove it. We get $G_2$ Step 3. Now in $G_2$ nodes $B$ and $D$ have no indegree so remove them.

49

If $T_1$ and $T_2$ are distinct minimum spanning trees, then consider the edge of minimum weight among all the edges that are contained in exactly one of $T_1$ or $T_2$. Without loss of generality, this edge appears only in $T_1$, and we can call it $e_1$. Then $T_2 \cup \{ e_1 \}$ must contain a cycle, and one of the edges of this cycle, call it $e_2$, is ...

45

A subgraph $H$ of $G$ is called INDUCED, if for any two vertices $u,v$ in $H$, $u$ and $v$ are adjacent in $H$ if and only if they are adjacent in $G$. In other words, $H$ has the same edges as $G$ between the vertices in $H$. A general subgraph can have less edges between the same vertices than the original one. So, an induced subgraph can be ...

45

Yes, Wolfram is wrong in this case. I just checked the archives of the Journal of Combinatorial Theory (where the erratum to the paper in question is published) and the two top vertices are supposed to be connected by an edge. I cannot provide a link because it requires a login, and I was able to log in through my university's subscription to the journal.

45

This is a bipartite graph. Colour the three middle vertices red and the other four vertices blue. Each path in the graph has vertices alternating in colour. So any Hamiltonian cycle has an equal number of red and blue vertices...

44

A few people have commented that all of the answers given so far have been identical up to symmetry (either by exchanging colors, or by using a symmetry of the uncolored diagram). Here's a proof that the answer that everyone has given is the only possible answer, up to symmetry. Let me number the regions, like so: Without loss of generality, assume that ...

41

This question already has a number of nice answers; I want to emphasize the breadth of this topic. Graphs can be represented by matrices - adjacency matrices and various flavours of Laplacian matrices. This almost immediately raises the question as to what are the connections between the spectra of these matrices and the properties of the graphs. Let's call ...

37

This is the subject well-known open problem called the Hadwiger-Nelson Problem. The problem asks for the exact minimum number of colors that we can color the plane with, so that no two points of distance one are the same color. You have observed that we cannot do it with only 2 colors, and asked, can we do it with 3 colors? The answer to that is no as well: ...

34

Such graphs exist for any (non-zero) integer. In fact, the arrows reflect two basic operations $\bmod 7$: The black arrows represent adding one (note that they go up from $0$ to $6$ and then cyclically back to $0$ again) Similarly, the white arrows represent multiplication by $10$; note that $5$ goes to $1$, and this reflects the fact that $5\times10=50\... 34 There are$2n(n+1)$potential edges in the grid, but some of them need to be left out because the grid points on the boundary have only$3$potential edges meeting, and only two of them can be in your path. Additionally, one of the edges incident to the start and end node must be left out. If we count the number of left-out half-edges we get at least$$4(... 34 The minimum is two states that use the fourth color. Nevada and its five neighbors cannot be colored with only three colors, and similarly West Virginia and its five neighbors cannot be colored with only three colors. In both cases, once you color the center state one color (say, red), you can't use it again on its neighbors: without using green, they'd have ... 32 This works, as you can check.. 32 We can prove this by finding a more complicated set of points that cannot be colored. One example is known as the Moser spindle: (The lines mark points that are one unit apart.) Suppose we try to color these seven points with three colors. Color the point$4$at the top of the diagram one of them - say, red. Then$3$and$6$have to be different both from$...

31

If the preliminary tail is length $T$ and the cycle is length $C$ (so in your picture, $T=3$, $C=6$), we can label the tail nodes (starting at the one farthest from the cycle) as $-T, -(T-1),..., -1$ and the cycle nodes $0, 1, 2, ..., C-1$ (with the cycle node numbering oriented in the direction of travel). We may use the division algorithm to write $T=kC+r$...

31

It's not planar. If you delete the vertex $j$ and the edge $bf,$ what's left is homeomorphic to $K_{3,3}.$

Only top voted, non community-wiki answers of a minimum length are eligible