Hot answers tagged

11

Your description of how the hydra "regenerates" is incorrect. You don't add copies of the entire tree above the grandparent node, only part of the tree above the grandparent node that starts with going to the parent node. This means that after cutting off a head from $((xx)(xx))$, you get $((xx)(x)(x))$, because you only duplicate the $(x)$ part you had ...


9

$\binom{n}{2}$ is the number of potential edges in a graph with $n$ vertices. Every subset of the set of edges makes a graph, so there are $$ 2^{\binom{n}{2}} $$ graphs. That grows pretty quickly.


8

Yes there are quite a lot actually, see for example Trinajstic's book Chemical Graph Theory. http://docdro.id/L3DrG6B or https://www.scribd.com/doc/313337501/Chemical-Graph-Theory-Trinajstic To list some of the topics discussed in the book verbatim, we have for example: Kekule structures Hückel theory the conjugated circuit model Zagreb group Cayley ...


7

While topology is "implemented" using open and closed sets, etc., it is ultimately the study of properties that are invariant under continuously stretching things. Since you're modding out by so many transformations, it has a distinctly qualitative flavour, and thus captures many of our intuitions that might be otherwise hard to write down without its ...


6

$K_{3,3}$ is a minor of $Q_4$, hence $Q_4$ is not a planar graph, and obviously $Q_4$ is a minor of $Q_n$ for any $n>4$, hence the only planar hypercubes are $Q_n$ with $n\leq 3$. Another approach: $Q_4$ is a triangle-free graph, but any planar and triangle-free graph with $n$ vertices has at most $2n-4$ edges. $Q_4$ has $16$ vertices and $32>2\cdot ...


5

In addition to the first answer, I think it's worth mentioning that the more meaningful quantity here is not the number of all graphs on $n$ labeled vertices, which is $2^{{n\choose 2}}$ as already pointed out, but the number of non-isomorphic graphs on $n$ vertices, since for example there are $n!/2$ ways that the same graph $\cdot\to \cdot \to \ldots\to ...


4

Yes, you are checking whether there is an automorphism of $G^{\prime} = \bar{G}_{1} \cup \bar{G}_{2}$ that swaps a vertex of $\bar{G}_{1}$ with a vertex of $\bar{G}_{2}$. You are using Graph-Aut as an oracle, so what you will do is use Graph-Aut to find the automorphism group of $G^{\prime}$ (returned as a set of generators), then just look at whether any of ...


3

The minimum number of edges that need to be removed to disconnect the graph is $3$, and there are just $4$ ways to do this: remove all of the edges incident at one vertex of degree $3$. There are $9$ ways to remove a set $E$ of edges so that (a) the resulting graph is disconnected, and (b) removing any proper subset of $E$ leaves a connected graph. However, ...


3

Euler path finding algorithm: STEP $1$: Locate the two vertices of odd degree. Pick one of them at random. STEP $2$: Start walking from the chosen vertex. Make sure you don’t use the same edge twice. Continue until you get stuck - this can only happen when you visit the other odd-degree vertex and have used up every edge through it. STEP $3$: Remove from ...


3

Maximal planar graphs are triangulated, so we know that each face has degree $3$. By the handshaking lemma (for faces), we conclude that $$3F = 2E,$$ where $F$ and $E$ are the total number of faces and edges respectively. Likewise, the handshaking lemma (for vertices) tells us that $$\frac{3V}{3} + \frac{4V}{3} + \frac{5V}{3} = 4V = 2E.$$ Finally, Euler's ...


2

Hints: The $\binom{n-1}{2}$ refers to the number of unordered pairs of vertices selected from the first $n-1$ vertices. We have $2$ raised to this power because for each such pair of vertices, we can either choose for them to be connected by an edge or not. The $n^{\text{th}}$ vertex is used to make sure that every vertex has even degree. Can you use this ...


2

To form exactly $k$ couples, select $\binom nk$ partners on either side and marry them in $k!$ different ways. Thus the total is $$ \sum_{k=0}^n\binom nk^2k!\;. $$ This is OEIS sequence A002720 (lots of information in that entry). According to Wolfram|Alpha, it's also $U(-n,1,-1)$, where $U$ is the confluent hypergeometric function of the second kind. ...


2

Let $C$ be the smallest odd cycle in $G$. Note that $C$ has no chords (i.e. edges between its vertices that aren't part of the cycle), as otherwise there would be a smaller odd cycle. Hence we can color $C$ with $3$ colors, and it will be a valid partial coloring of G. Now if we throw all the vertices in $C$ from $G$, the remaining graph is bipartite ...


2

We can do better. In fact, we will have $\chi(G) \le 3$ for such a graph. First, a lemma. Lemma: Let $G$ be a graph with no odd cycles. Then $G$ is $2$-colorable. Proof: Pick an arbitrary vertex $v\in G$. Color all vertices an even distance away from $v$ one color, and an odd distance away from $v$ another color. Note that this coloring is well defined ...


2

Now if $Q$ an increasing graph property (if $G \in Q$, then the graph obtained by adding any arbitrary edge to $G$ is also in $Q$) such that the null graph on $n$ vertices is not in $Q$ and $K_n$ is in $Q$, then $$ p \rightarrow f(p):=Pr ( G(n,p) \in Q ) $$ is a strictly increasing function with $f(0)=0$ and $f(1)=1$. This is because for fixed $n$, $$ f(p) ...


2

The definition of the fundamental group does not depend on any choice of a spanning tree. A spanning tree is just used to get an explicit description of a group that the fundamental group is isomorphic to. So it would be no problem if it turned out you could get free groups of different rank by choosing different spanning trees--this would just be a proof ...


2

Your definition of automorphism is a bit too strong, I feel. Leaving something "unchanged" in the sense that the numbers in each cell of a matrix is a VERY strong notion of equality. However, you're not using that definition of equality for graphs. As corrected by Morgan Rodgers, strict equality actually works fine. The adjacency matrices are indeed ...


2

You can label each vertex $V= \{v_1,\cdots,v_6\}$ and then create the adjacency matrix $$A_{i,j}=\left\{\begin{array}{rl} 1 & v_i \text{ and } v_j \text{ share an edge} \\ 0 & \text{ otherwise} \end{array}\right.$$ Then find the eigenvalues of $A$ computationally using Mathematica, WolframAlpha, or Matlab (or any other program you'd like).


1

$\pi_1(A)$ and $\pi_1(B)$ are trivial since they are contractible, $\pi_1(C)$ is the free group generated by 2 elements since $C$ retract to the bouquet of two loops.


1

The number of strings of length $n$ having exactly two blocks of $1$'s, the first of length $a$, the second of length $b$, is readily computed to equal $n+1-a-b\choose2$, provided $n\ge a+b$. This gives us the number of vertices as $$v_n={n-1\choose 2}+2{n-2\choose 2}+3{n-3\choose 2}+2{n-4\choose 2}+{n-5\choose 2} =\frac{9n(n-7)}{2}+60$$ To count the edges, ...


1

The ($\Rightarrow$:) part is almost complete, except where you are not sure. We pick $x \in X$ and $y \in Y$, and we know that there is a path between them. Let the vertices in this path be $x, a_1, a_2, \dotsc, a_n, y$. The first vertex is in $X$, and the last vertex is in $Y$; all vertices are either in $X$ or $Y$ and never in both. Consequently, there ...


1

What does each column $b_j$ of B encode, geometrically? Can you show that $b_i\cdot b_j$ computes the number of edges that vertex $i$ and $j$ share? The theorem should now be straightforward: consider the three cases where two vertices $i,j$ are adjacent, not adjacent, and equal.


1

I disagree with Hagen that you have the right idea. It is a serious logical error you made concerning induction, and I encourage you to read and fully grasp http://matheducators.stackexchange.com/a/10034/1550 before attempting induction problems. After you read that then read my answer. I give you any tree $T$ and graph $G$ such that every vertex in $G$ has ...


1

You have the right idea, but you should not modify $G$, esp. you cannot expect to obtain a given degree-$e$ graph from an unspecified degree-$(e-1)$ graph. Instead try the following: Let $T=(V_T,E_T)$ be a tree with $|E_T|=e$ edges (and hence $|V_T|=e+1$ vertices) and let $G=(V_G,E_G)$ be a non-empty, simple graph be given such that all vertices of $G$ ...


1

You're right, that's not very convincing. :-) There are essentially two different trees with $3$ edges. You can have all three edges incident at the same vertex; this is the star graph $S_3$. Or you can have at most $2$ edges incident at any vertex – then the tree is the path graph $P_4$ (why?). $S_3$ is easy. The claim isn't quite right since it ...


1

Archaick has already given you a simple exposition of your correct approach. I would like to point out an interesting fact, which is that it is actually crucial to use the Eulerian property of $G$, which proceeds via the theorem that every finite graph with even vertex degrees has an Eulerian loop, and hence any two vertices are in some cycle. The reason is ...


1

Perhaps this is just me being pedantic but the argument I think you're trying to make wasn't very clear to me upon the first reading. Is this what you mean? Note that since every such graph has an Eularian cycle, there necessarily exist two paths for each vertex to every other vertex which have no edges in common. Thus removing any single edge cannot ...


1

The question you should ask (yourself) is: What is the graph-theoretic interpretation of the matrix product $C^T C$? Try to answer this, and you will get the answer. If you fail to find the answer, read further… Notice that the $(i,j)$-entry of this product will be the "dot product" of the $i$-th and $j$-th columns of the incidence matrix $C$, which ...


1

If there are no cycles, you have a tree, but a tree on $n$ vertices has $n-1$ edges. So there is at least one cycle. Now if you take a cycle in your graph and remove one edge of that cycle, you have a connected graph with $2015$ vertices and $2014$ edges, and a connected graph with $n$ vertices and $n-1$ edges is a tree (prove by induction on $n$, using ...



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