Tag Info

New answers tagged

1

It seems the following. It is clear that for a tree $T$ $\min_i f_i(T)=\min {(i,j)\in E(T): X_i+\frac {X_i}{X_i+X_j}}$, where $E(T)$ is the set of edges of the tree $T$. Let $X_1\le X_2\le\dots X_n$. Then $\min_i f_i(T)\le X_1+\frac {X_1}{X_1+X_2}$, and the maximum is reached when the nodes corresponding to 1th and the 2nd invectors are connected by an ...


0

What you want to do is prove that every vertex has even degree. Assume that one vertex, $v$, has odd degree. You know that it has an odd number of common neighbours with every other edge. This means that if it is adjacent to vertices $\{v_1, \dots v_i \}$, then it is adjacent to vertex $v_1$ and and odd number of other vertices, vertex $v_2$ and an odd ...


0

What about a more direct approach: what can you say about the degree of every vertex if your graph meets your given criterion? Recall that a graph is Eulerian iff every vertex has even degree. You would have two cases to consider: either your vertex pair are adjacent or they are not. Not sure if it is any better than what you suggested in your post, but it ...


2

Yes. Remove the bridge and let $H$ be one of the resulting components; I claim that $\chi'(H)=4$. $H$ has one vertex of degree $2$ and $2n$ vertices of degree $3$, so $H$ has $3n+1$ edges. If the edges of $H$ are colored with $3$ colors, then there must be at least $\lceil\frac{3n+1}3\rceil=n+1$ edges of one color. Since edges of the same color can't be ...


1

From the context you provided, it seems that the definition of $\tau(A)$ is given in the sentence you quote: $\tau(A)$ is the number of connected components of the graph $G\setminus A$, obtained by removing from $G$ a subset $A$ of its vertices.


3

Note: "Prove the existence of a maximum matching." That is not to say that every maximum matching saturates $v$ (it is possible that some do not). Consider any maximum matching, $M$ (guaranteed to exist). Either $v$ is saturated in $M$ or it isn't. If it is, then we are done and the matching we are looking at satisfies the claim. Suppose then that $v$ ...


4

Take three vertex-disjoint triangles. Add a tenth vertex, and edges joining it to one vertex in each of the three triangles.


1

The maximum number of edges is clearly achieved when all the components are complete. Moreover the maximum number of edges is achieved when all of the components except one have one vertex. The proof is by contradiction. Suppose the maximum is achieved in another case. Then there exist two components with more than one vertex say the number of vertices are ...


1

Case 1: degree 3. We construct a sequence of graphs with only ``triangular'' faces. Let $G_0$ be a triangle, it has 3 vertices and 2 triangular faces. Having constructed $G_n$, we take an arbitrary triangular face, add a vertex in the middle and connect it to the three corners of the triangle. This procedure adds 1 vertex and 2 faces. We conclude that ...


4

We begin with Euler's formula: $v-e+f=2$. We know there are $v=34$ vertices. We can find another formula by counting the number of face-edge pairs in two different ways: by considering (a) for each face, the number of boundary edges, and (b) for each edge, the number of neighboring faces. We solve this system of linear equations to find $f$, and hence ...


1

Going off the bipartite graph hint, you can also look at the eigenvalues of the adjacency matrix. Note that $tr(A) = \sum_{i} \lambda_{i}$, where $A$ is the adjacency matrix and $\lambda_{i}$ are the eigenvalues. Note $tr(A)$ is the trace of $A$, which is the sum of the diagonal entries. So: $\sum_{i=1}^{5} \lambda_{i} = 0$. We also have: $\sum_{i=1}^{5} ...


4

Hint: a triangle free graph on $5$ vertices is bipartite unless it contains a $5$ cycle. But if it has a $5$ cycle and is triangle free it is a cycle. Hence you want to find the bipartite graph with five vertices with the most edges.


4

Consider a pentagon. If you try to add any more edges to the pentagon a triangle will be formed. Thus for graph having a cycle containing 5 vertices ( all vertices that is ) can have at maximum 5 edges without violating the condition. Now consider bi-partite graphs with a total of 5 vertices , say $x$ in one group and $5-x$ in other. Bipartite graphs can't ...


2

It is not true that this is $5$. Connect one point to three points, and connect the remaining point to the same three points. To proof this optimal you could start distinguishing cases by maximum degree of a vertex. There might be a more elegant argument yet I would not know it momentarily.


3

A sequence is graphic if and only if the sequence obtained by deleting the largest degree $k$ and subtracting one to the $k$ largest degrees remaining is graphic.Try to prove this by induction. hence you get $8,8,7,7,6,6,4,3,2,1,1,1$ is graphic $\iff$ $7,6,6,5,5,3,2,1,1,1,1$ is graphic $\iff$ $5,5,4,4,2,1,0,1,1,1$ is graphic $\iff$ $4,3,3,0,0,1,1,1,1$ is ...


0

Construct the Strongly Connected Components graph (this can be done in $O(|E|+|V|) \le O(|V|^2$)). You can then calculate which nodes is reachable from every node naively in $O(|V|^2)$ from this graph.


1

While your linear program is a valid formulation of the max flow problem, there is another formulation which makes it easier to identify the dual as the min cut problem. Let $(G,u,s,t)$ be a network with capacities $u: E(G) \rightarrow \mathbf{R}^+$, source vertex $s$ and sink vertex $t$. Let $P$ be the set of all simple $(s,t)$-paths in $G$. Suppose we ...


0

If your graph has $4$ edges, it must be a tree (a tree is a graph with no cycles). To see this, notice that if it had a $5$-cycle it would have $5$ edges, if it had a $4$-cycle it would have no edge connecting to the vertex outside the cycle, and if it had a $3$-cycle it would be disconnected, either because the $4$th edge connects the two other vertices and ...


0

The diagram would be like For an edge to be placed remember that you must choose $2$ vertices and be careful about bijection, by that i mean that if you do not label the vertices this two graphs (see below) are identical. Edit: As commented, because they are just a few, you can iterate all the ways (without order i.e. $2+2+2+1+1=2+1+2+2+1=\ldots ...


0

For $4$ edges: $${\rm X}\qquad {\rm W}\qquad \vdash$$


2

What text are you using? Doesn't your text say that the vertex set is nonempty? If it doesn't, it should; recognizing the "null graph"" (with no vertices) as a graph is a bad idea. (By the way, the term "empty graph" is often used to mean a graph with no edges) Your example proof does not use mathematical induction in the form "if $P(n)$ implies $P(n+1)$, ...


2

The concept of "strongly connected" and "weakly connected" graphs are defined for directed graphs. A digraph is strongly connected if every vertex is reachable from every other following the directions of the arcs. I.e., for every pair of distinct vertices $u$ and $v$ there exists a directed path from $u$ to $v$. A digraph is weakly connected if ...


3

The discharge method works here. (You can forget this proof, but try to remember the method. It can be very powerful. It belongs in your toolbox next to the pigeonhole principle and the principle of induction). Assume $G$ is a counterexample with a minimum number of vertices ($n$). We may also assume that we have maximized the number of edges ($e$). So $G$ ...


2

After a quick glance of the linked doc: It seems that the author wants to teach dynamic programming. The approach involves a recursive solution which is then likely to be optimised with memoisation techniques (reuse of once calculated results). Induction is a natural choice for proving a recursive method, because of its related structure (inductive step = ...


1

That you don't create new matrices $D^{(n)}$ but just modify the values in the one matrix. Well, not in one matrix but you have two where one is the previous one ($D^{(n - 1)}$) and the second is the one you compute. When a new $D^{(n)}$ is computed, it becomes $D^{(n - 1)}$ in the next iteration and the previous $D^{(n - 1)}$ (now $D^{(n - 2)}$) becomes a ...


2

In an arbitrary planar graph, if we draw it in the plane, each face will be bordered by $\geq 3$ edges. In the bipartite case, however, it must be $\geq 4$ edges (a $3$-edge face is a triangle, which would contradict the graph being bipartite).


2

The number of vertices of odd degree is even in any finite simple graph.This is because the sum of the degrees of the vertices is twice the number of edges(hence even). Since this sum is even there is an even number of vertices of odd degree.If there is an even number of vertices of odd degree and $99$ vertices we conclude there is an odd number of vertices ...


1

I suppose you want to consider subsets $S$ such that $|S| \leq |G|/2$. You are asking for the edge expansion of the 1-skeleton of the permutohedron of order $n$. Equivalently, it's the Cayley graph of symmetric group $S_n$ under the generators $(12), (23), \dotsc, (n-1,n)$. Let's write $G_n$ for the $n$-th graph and $h(G_n)$ its edge expansion. I present a ...


1

I would like to contribute some ideas even though I don't have as much time as I'd like at the moment. If I understand this problem correctly then the class of graphs under consideration call it $\mathcal{Q}$ is in a set-of relationship with the class of endofunctions call it $\mathcal{E}$ with the latter being sets of the former. This gives the ...


1

Let $G$ be a simple, planar graph with $p$ vertices, $q$ edges, and $r$ regions. For part one: Let $r_n$ be the number of regions bounded by $n$ edges. Then $$2q=r_1+2r_2+3r_3+\cdots+nr_n=3r_3+\cdots+nr_n\geq3(r_1+r_2+\cdots r_n)=3r$$ since $G$ is simple (no loops or multiple edges means that $r_1=r_2=0$). So $r\leq 2q/3$. Now $$2=p-q+r\leq ...


0

1) Suppose to the contrary that all vertices have degree at least $6$ and the graph $G$ is planar. By the Handshake Lemma, there are at least $3v$ edges. By a corollary to Euler's formula, we have $e \leq 3v - 6$, a contradiction. And so there must exist at least one vertex of degree at most $5$. 2) I will have to think more on this and will edit if ...


1

The first claim can be proved using Euler's formula: for a finite, connected planar graph with $v$ vertices, $e$ edges and $f$ faces, $v - e + f = 2$. The second claim is the well-known four-color theorem. As noted by Johanna in the comments, it seems unlikely that you would be asked to prove this as an exercise. The third claim can be proved by applying ...


2

It seems the following. You are right, this is an optimal bound as shows the following example. The set $B$ consists of 5 copies of the following hexagonal graph. To each monochromatic triangle corresponds a vertex from the set $A$, connected with the vertices of the triangle.


4

Every vertex of $A$ covers 3 vertices of $B$, and at most covers 3 pairs of edges forming a triangle. So, to reach the lower bound of $|A|=20$, it suffices that $B$ is a $4$-regular in $30$ vertices such that its edges can be partitioned in triangles. Using this condition, doodling a bit in a piece of paper we reach this graph: It can be covered by 10 ...


0

It's true. It follows from the submodularity of the (directed or not) graph cut function with non-negative weights. To prove it, I think the only useful advice it to work in cases: given a graph with edge weight function $\delta$ and two sets $S$ and $T$ of vertices, separate the cases of the edges going from $S \setminus T$ to $T \setminus S$; from $S ...


0

Taken from Wikipedia: A clique in an undirected graph $G = (V, E)$ is a subset of the vertex set $C \subseteq V$, such that for every two vertices in $C$, there exists an edge connecting the two. What's hidden in this definition is that you must take two different vertices. Otherwise cliques wouldn't even exist. Is it true that for any $x,y \in K_1$, ...


3

Yes, you are correct as you've written your question, but let's be careful with terminology. A maximal clique means a clique that isn't contained in any larger clique in $G$. So isolated vertices in $G$ (which are $K_1$'s) are certainly maximal cliques. On the other hand, a maximum clique is a clique in $G$ of largest possible size. So if $G$ has at least ...


2

Let's think of edges in $\mathcal{A}$ as being coloured red, and the edges in $\mathcal{B}$ as being coloured blue. Notice that $\mathcal{A}\cup\mathcal{B}$ is a disjoint union of paths of length $1$ (i.e., corresponding to edges that are in both $\mathcal{A}$ and $\mathcal{B}$), paths of length $\geq 2$, and cycles, where for each cycle or path of length ...


5

Consider the complete graph $K_4$ on vertices $a,b,c,d$. Then the set of edges $ab,bc,cd$ is a spanning tree: a path of length $3$. But the set of edges $ab,ac,ad$ is another spanning tree, different (in the sense of not isomorphic) from the first since it has a vertex of degree $3$. Here is a picture, with the two trees in red:


1

It doesn't make sense to talk about an individual graph being non-isomorphic. Informally, two graphs are non-isomorphic if they are structurally different. If we have two graphs $G_1$ and $G_2$, then if $G_1$ is bipartite and $G_2$ is not bipartite, then they are non-isomorphic. (I'm guessing this is the link between the two topics you've encountered.) ...


0

As mentioned in the comments, the definition you want is a weighted directed graph.


3

What they are saying is somewhat true: A connected graph can be regarded as a metric space (when equipped with the graph metric) and as such can be used for approximation of geometry of Riemann surfaces (say, hyperbolic ones) as well as higher dimensional Riemannian manifolds. When done properly, one can derive some conclusions about, say, spectral ...


2

The graphs you are describing are known as simple (directed) pseudotrees; see http://en.wikipedia.org/wiki/Pseudoforest. There doesn't appear to be a 'nice' closed form for these trees. Wikipedia/OEIS gives the number of undirected connected graphs with $n$ vertices as $$f(n) = \sum_{k=1}^n \frac{(-1)^{k-1}}{k} \sum_{n_1+\cdots+n_k=n} \frac{n!}{n_1! \cdots ...


1

My solution does not agree with your answer for $T(5)$, but let's give it a try anyway . . . To construct such a graph on $n$ vertices, consider the vertices with indegree $0$. If there are none of these then the graph is a (directed) cycle, and there are $(n-1)!$ possibilities. If there are $k$ specified vertices with indegree $0$, then we obtain our ...


0

You can turn an algorithm for constructing an object into an existence proof as follows: State the algorithm Prove that the algorithm eventually terminates Prove that the result of the algorithm satisfies the desired properties Your algorithm can be described in pseudocode as follows: SPANNING_TREE(G): let H = G while H contains an edge e whose ...


0

Let $f(n)$ be what you want. Denote a graph acceptable if it's connected components (when viewed as an undirected graph) Are all good.(This is the same as saying it is of regular out-degree 1) Then the number of acceptable graphs is $(n-1)^n$. But we can also count the number of acceptable graphs by classifying on the number of vertices in the connected ...


0

The $4 \times 4$ lattice has $K_{2,4}$ as a topological minor. Suppose we label the vertices of $K_{2,4}$ as $\{x,y\}$ and $\{a,b,c,d\}$. The red edges of the drawing show a subdivision of $K_{2,4}$ as a subgraph of the $4 \times 4$ lattice.


2

You know already that you have $m+n$ vertices and $mn$ edges in your graph. If you want your subgraph to contain $m+n$ vertices, then $G'$ will contain all vertices of $G$. Because of this every edge of $G$ can be in $G'$ (if we delete one vertex, the edges incident with this vertex can not be in $G'$). So for every edge $e$ of $G$ we have two ...


1

If a matroid of rank $m$ over a ground set of $n$ elements is representable over a field $F$, then it is representable by a matrix of the form $[I^m | B ]$, where $B$ is a $m \times (n-m)$ matrix over $F$. Also, any matrix representation can be transformed to one of this form by performing elementary row operations and (possibly) deleting rows. To see why, ...


1

It's the sequence A001429 in the OEIS.



Top 50 recent answers are included