Tag Info

Hot answers tagged

16

Consider a hexagonal tiling of the plane, and subdivide each hexagon into six equilateral triangles. Now all the vertices have degree six, albeit with an infinite number of vertices. If you are willing to settle for merely a high proportion of vertices with degree six, consider truncating the tiling at a large radius $R$ from the origin. The vertices ...


7

Take a regular icosahedron whose edges are unit length. For any $n > 1$, subdivide each of its face into $n^2$ equilateral triangle with edge length $1/n$. You obtain a polyhedron with $10 n^2 + 2$ vertices, $30n^2$ edges and $20 n^2$ faces. Using stereographic projection from the center of one of its face, it is easy to see the vertices and edges of ...


7

My computer graphics are not up to scratch, so please bear with me. Here are 8 basic hexagons: $$A=\matrix{&1&\cr6&&2\cr5&&3\cr&4&\cr};\quad B=\matrix{&4&\cr3&&5\cr2&&6\cr&1&\cr};\quad C=\matrix{&4&\cr5&&3\cr6&&2\cr&1&\cr};\quad ...


3

The following is a supplement to the nice answer of @GerryMyerson. It was inspired by the visually pleasing and inspiring representation of his solution. When looking at his solution we can analyse the $8$ hexagons with respect to symmetry the tesselation with respect to the relationship between hexagons and their neighbours We start with ...


3

Each of the three pictures they show are of completely different decompositions. Restrict your attention for the moment to just the far left image. In this graph, they have colored the edges three ways (in the original picture as thick lines, thin lines, and dashed lines). If you look at each color class individually, they are all isomorphic to the ...


3

Filling in the gap (this was asked in the problem (***) and proves item 4 below): We will write $n(G)$ for $|V(G)|$ and $e(G)$ for $|E(G)|$ and $a(G)$ for $\frac{e(G)}{n(G)}$. If $G$ does not contain a vertex $v$ with $d(v)<a(G)$, then $\delta(G)\geq a(G)$ and we are done. Otherwise we produce a graph $G_2$ by removing a vertex $v$ with $d(v)<a(G)$. ...


3

In other words you are asking if a graph and its complement can both be connected? Sure they can. For example, take any self-complementary graph: the $4$-point path $P_4$, the cycle $C_5$, etc.


3

27 = 3*3*3, so maybe we have to work with triangles. A triangle has three spanning trees. Let's take three triangles and try to connect them in such a way that we get 27 spanning trees and 8 edges. Call them triangle A, B, C. Connect triangle A and B together so that they share a vertex. Now we have 8 vertices. Connect a vertex from triangle C to the ...


2

This might be an extension of the marriage theorem, except that any group of n passengers needs to be friends with at least $\left \lceil \frac{n}{4}\right \rceil$ drivers.


2

Euler's formula for Planar graphs, I think. EDIT: To clarify further, here m (nbr of loops) corresponds to (number of faces - 1), since we do not count the infinite face bounded outside the circuit.


2

Is the part where we take out a vertex and then connect it back to all other vertices legit? Yes, but I think it could be a bit clearer: For clarity, I’d define $E_n$ to be the set of edges on such a graph with $n$ vertices. That way, in the inductive step, you can talk about $E_{n-1}$ and $E_n$ without any risk of confusion. Just include a line about ...


2

The graph is planar, so imagine it's embedded in the plane. Stand at some vertex in the plane. There are, say, seven edges emanating from you (like spokes radiating from the hub of a bicycle wheel), and they can be ordered, say, clockwise (but the order "wraps around" when you get back to the beginning). So their colors, in order, might look like 1 2 3 4 5 ...


2

It’s easier to understand if you word backwards. Suppose that such a tree has depth $d$; what are the maximum and minimum possible numbers of nodes? A perfect binary tree of depth $d$ has $$1+2+\ldots+2^d=2^{d+1}-1$$ nodes; that’s clearly the maximum. You can remove at most $2^{d-1}$ of the nodes in the last level and still have a quasi-complete binary ...


2

Let $S$ be a minimum vertex cover. Give every vertex of $S$ a different color. Finally give all vertices of $V-S$ the same, new color. I trust, you can take it from here.


2

In general for a graph with $n$ vertices, there are ${n \choose 2}$ possible edges. If you want a graph with $k$ edges, you simply choose $k$ edges from the pool of ${n \choose 2}$ possible edges. Thus the number of labeled graphs having $n$ vertices and $k$ edges is $${{n \choose 2} \choose k}$$ In particular, for $n = 4$ and $k = 1$, you get $${{4 ...


1

A bipatite graph with a bipartite complement will be very rare. At the very least, both the graph, and its complement must not have a triangle. This means the graph cannot have $6$ or more vertices (the Ramsey number $R(3,3)=6$). There are triangle-free graphs with triangle-free complements on $5$ vertices, but they are isomorphic to a $5$-cycle (which is ...


1

The graph without the purple lines is planar. Let's call it $H$. If you add one purple line, you immediately find a subdivision of $K_5$, so $H+e$ is not planar anymore. But then $H$ is a maximal planar subgraph and $cr(G)\geq |E(G)|-|E(H)|=3$.


1

HINT: Use the definition to prove by induction that every tree is connected, and no tree contains a cycle. Then prove the contrapositive of the desired statement. Assume that a graph $G$ is not a tree; either it contains a cycle, or it’s not connected. If you know that it contains no cycle, then it must not be connected. Now show that there must be a pair of ...


1

See this question for a proof that a connected graph is a tree defined in this manner if and only if it has no cycles. Thus the only way $G$ can fail to be a tree is for it to be disconnected. If $G$ is disconnected into two nonempty components $G_1$ and $G_2$ with no edges between them, then adding any edge from a vertex in $G_1$ to a vertex in $G_2$ will ...


1

Let $\mathcal G$ be a collection of graphs ,then a $\chi$-binding function is a function from $\mathbb N$ to $\mathbb N$ such that for any graph $G\in \mathcal G$ we have that the chromatic number of $G$ is less than or equal to $f(\omega(G))$ , where $\omega(G)$ is the clique number of $G$. Examples of some trivial functions $f$ that are always binding ...


1

Your question is quite broad, but I agree with Modded Bear that AP calc is unlikely to be of much help. The Concrete Mathematics book would be excellent, but I might throw in the book Discrete Mathematics and Its Applications by Kenneth Rosen. This book is an absolute tome with thousands of exercises (literally) that range from the very easy to the ...


1

I would consider Mathematics of Choice by Niven and Graphs and Their Uses by Ore. http://www.maa.org/publications/ebooks/anneli-lax-new-mathematical-library These books are part of a series intended for talented high schoolers, and the authors were first-rate mathematicians.


1

If I interpret the lemma and the definitions correctly, it seems that there are two definitions at work here: The code of an ordered rooted tree works through the branches "from left to right", i.e., following the order. The minimum code of an ordered rooted tree works through the branches on a "smallest binary number first" basis. While the code ...


1

See the first paragarph on page $4$ of the Electronic Edition $2000$: If $U$ is any set of vertices (usually of $G$), we write $G-U$ for $G[V\setminus U]$. In other words, $G-U$ is obtained from $G$ by deleting all the vertices in $U\cap V$ and their incident edges. ... Instead of $G-V(G')$ we simply write $G-G'$.


1

By coincidence this was proved yesterday on Girth and monochromatic copy of trees The first part of the answer shows that every graph $G=(V,E)$ has a subgraph with minimum degree at least $\frac{|E|}{|V|}$, which is half of the average degree. I trust you can take it from there. (ADDED) Assume the average degree of our $k$-degenerate graph $G$ is larger ...


1

Try to understand the Hajós construction in terms of edges and vertices first. The WIKI article is clear and elementary, so you should be able to understand it. You will see that the Hajós construction is just a union with one vertex identification, one edge addition and two edge removals. Now you can start translating this into incidence matrices. Your ...


1

Clearly a tree with 1 vertex has no cycles. For a connected tree with $k$ vertices, pick a vertex that was most recently added in some sequence constructing the tree. If we remove the vertex, there are no cycles by induction. If we had a cycle when we attached the new vertex, then the cycle would have to contain the new vertex, which means the new vertex ...


1

This proof also works to show that outerplanar graphs have at most $2n - 6$ edges. Which is not true so your feeling is right - something is missing :) The problem is that $H$ has $n + 1$ vertices. So you need $m_H > 3(n + 1) - 6$ to show that $H$ is not planar. But you just need to modify your proof a little bit, by saying $m_H > 3n - 3 = 3(n + 1) - ...


1

In list coloring, different vertices can have different lists, while if you're just $k$-coloring a graph, then every vertex has the same $k$ colors available. There are bipartite ($2$-colorable) graphs with arbitrarily high choice number.


1

The difference is that when you talk about ordinary vertex colorings, each vertex has the same allowed list of colors: all of the colors that are available. A list assignment can assign a different set of allowed colors to each vertex; there’s a specific example in this Wikipedia article showing a list assignment to the vertices of $K_{3,27}$ in which each ...



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