Tag Info

Hot answers tagged

4

This is called a bipartite (or 2-colorable) graph.


3

This seems to be true. Note that if $K \subset \mathcal{O}$ then $\bigcup K$ is an open subset of $X$. Also, if $K_1$ and $K_2$ are (the vertex sets of) distinct components of $\mathcal{O}$, then $\bigcup K_1 \cap \bigcup K_2 = \emptyset$. Thus the decomposition of $\mathcal{O}$ into components induces a decomposition of $X$ into open sets.


3

Yes. Say $E_0\in\mathcal O$. Let $\mathcal O_0$ denote the set of $E\in\mathcal O$ such that $E$ is connected to $E_0$ by a chain of vertices in that graph. Let $\mathcal O_1=\mathcal O\setminus \mathcal O_0$. Let $V_j$ be the union of the $E\in \mathcal O_j$, $j=0,1$. So the $V_j$ are open and $X=V_0\cup V_1$. Now if $E\in\mathcal O_0$, $F\in\mathcal O$ ...


3

We need to look at Eulerian paths, and use the well-known result about them using odd and even vertices. This makes $f(12)=1$ and $f(15)=8$. The trains are fairly basic in the odd case (an even number of vertices) - we 'disconnect' $\dfrac{k+1}{2}$ single edge disjoint graphs, the remaining graph is Eulerian and can have a path joined to it to make a train, ...


2

Start with $\Delta \ge$ average degree $\ge \delta$ for any graph. We know that the total degree is $2m$ by the Handshake Lemma, so the average degree is $=\frac{2m}{n}$. So $\Delta \ge\frac{2m}{n}\ge \delta$. Now, let m divide all three sides, changing the $\ge$ to $\le$: $$\frac{m}{\Delta}\le\frac{n}{2}\le\frac{m}{\delta}$$


2

Trees: This is a tree, and, as you noted, there is a pendant vertex in the tree that can be removed without disconnecting the graph. All other connected graphs: Then this graph has a spanning tree, and you can remove one of the pendant vertices from the spanning tree. This clearly preserves some path between all the remaining vertices, because removing ...


2

Since $G$ is connected, there is a walk $W$ that passes through every vertex of $G$ such that the end vertex $v$ occurs exactly once in $W$ (we stop the walk when we've seen every vertex). Since $W \setminus v$ is a walk through every vertex in $G \setminus \{v\}$, it is also connected.


2

Intro There are some other constraints on $E,V,F$, regardless of whether the polyhedron is convex or not. In fact these hold as long as the polyhedron is simple (has no holes). If the polyhedron is simple -- this includes all convex polyhedra, then Euler's formula applies in its original form ($F + V - E = 2$); otherwise the right-hand side becomes $2 - ...


2

"Does this imply that the graph G is k-partite?" No. The simplest example is an odd cycle. See https://en.wikipedia.org/wiki/Mycielskian for examples of graphs with clique size 3 and large chromatic number. The condition that every vertex belongs to a clique of size $k$ is not relevant as dummy vertices can be added to form such cliques. "If not, what ...


2

Suppose $G$ is a graph in which any two vertices have at least one common neighbour, but no vertex is adjacent to all other vertices. Let $a$ be a vertex, $b$ a vertex not adjacent to $a$, and $c$ a vertex adjacent to both $a$ and $b$. By assumption, there is a vertex $d$ not adjacent to $c$ (and this can't be $a$ or $b$). A common neighbour to $a$ and ...


1

does this theorem have a common name? It is sometimes called König's Theorem (1936), for example in lecture notes here. However, this name is ambiguous.


1

If the graph is $K_1$ it is false since $m=0$ and $n=1$. Let $n\geq 2$: If the graph is a tree it has $n-1\leq 2n-3$ edges. We suppose the graph is not a tree: If you add the number of edges each face has you get $2m$. This sum is at least $3(f-1)+n$ since the inner faces have at least $3$ edges and the outer face has at least $n$ edges (since the outer ...


1

Proof that $\lceil \log_2 n \rceil$ bipartite graphs suffices. We label the vertices $\{0,1,\ldots,n\}$. For $i \in \{1,2,\ldots,\lceil \log_2 n \rceil\}$ we define the $t$-th bipartite graph to contain the complete bipartite graph with vertex bipartition $A \cup B$ with $A$ containing the vertices with $t$-th bit $1$, and $B$ containing the vertices with ...


1

In your example you’re taking $k=\frac12n(n-1)$. For this $k$ it’s certainly true that $n\le 2^k$; in fact, if $n\ge 3$, $\frac12n(n-1)\ge n$, so $2^k\ge 2^n>n$. Thus, your example is entirely consistent with the result in question. The point of the theorem is that (1) if $n\le 2^k$, then you can cover $K_n$ with $k$ bipartite graphs, but (2) if ...


1

The term Scale-free is many times (ab)used to refer to slightly different graphs. The working definition is to call any graph with an asymptotic power law distribution as scale-free. To understand the reason, consider an ER graph. The degree distribution of this graph follows a Poisson distribution and so it is highly peaked at value $<k>$. Hence in ...


1

I think a the complete graph on 3 vertices would work here as an example, so basically an equilateral triangle. Because the chromatic number is 3, but then all the subgraphs have chromatic number 2, because if you remove an edge from the triangle, then you only need 2 colors to color all vertices. I think this would work, unless there is something else that ...


1

Let $G$ be a directed graph with no self-loops in which every vertex has out-degree $1$. Suppose that the vertex $v_0$ is a source (i.e., its in-degree is $0$). Then there is a unique directed path-with-cycle $v_0,v_1,\ldots,v_k,v_\ell$ such that $\ell\in\{1,\ldots,k-1\}$. If no vertex of $G$ is a source, let $v_0$ be any vertex of $G$; then there is a ...


1

Let $M$ be the matrix of the graph, $t:E\rightarrow V$ be the target map and $s:E\rightarrow V$ be the source map, so that if $e$ is an edge linking $v_i$ to $v_j$ then $t(e)=v_j$, $s(e)=v_i$ and $Me=t(e)-s(e)$. If $e$ is any edge from $v_i$ to $v_j$, interpret $-e$ as the edge $e$ with the reverse orientation. That is the same edge but from $v_j$ to $v_i$. ...


1

Every arc in the graph adds $+1$ to the outdegree of exactly one node (the one from which it starts) and $+1$ to the indegree of exactly one node (the one where it arrives). So your sum is actually $$\sum_{e\in E} (+1-(+1))=0$$ Added: The above argument can be formalized using induction on the number of arcs: Base step: a graph with $0$ arcs. Inductive: ...


1

Let $A$ be the adjacency matrix of the graph. Then in and out degrees of $i$'th vertex are: $$k_{i}^{in} = \sum\limits_{j=1}^{n}A_{ij}$$ and $$k_{i}^{out} = \sum\limits_{j=1}^{n}A_{ji}$$ Hence both $\sum\limits_{i=1}^{n}k_{i}^{in}$ and $\sum\limits_{i=1}^{n}k_{i}^{out}$ are equal to the sum of all the elements of the adjacency matrix and so their ...


1

Use a computer. "Nauty and Trace" programs gives a computational procedure to solve this problem. This open source package is available from http://pallini.di.uniroma1.it/. Another helpful link may be http://www.dharwadker.org/tevet/isomorphism/


1

If there is exactly one vertex of odd degree there is no Euler walk, what you say is not possible, there must always be an end vertex. It is however true that no graph has exactly one vertex of odd degree this is becase the number of vertices of odd degree is always even. This can be proved by noticing the sum of the degree of the vertices is twice the ...


1

Variant 0 Clearly there are $n!$ possible configurations, which gives a trivial lower bound on the number of tries needed to distinguish all of them, since each try only gives $2$ cases. But like with comparison sorting, it is unlikely that we will ever be able to determine the optimal number of tries except for very small $n$. We can get to within a linear ...


1

Perhaps the easiest way to see it is to note first that since $d(x)\ge d(y)$ for each $xy\in E$, we must have $\frac1{d(x)}\le\frac1{d(y)}$ for each $xy\in E$. Thus, $$\sum_{x\in X,y\in Y,xy\in E}\left(\frac1{d(y)}-\frac1{d(x)}\right)$$ is a sum of non-negative terms, and as such is (a) non-negative, and (b) zero if and only if each term ...


1

Yes. Multiply the equation $\delta' f_E = f_V^2 \delta$ with $f_E^{-1}$ on the right and with $(f_V^{-1})^2$ on the left, and you are done.



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