Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [graph-theory]

Use this tag for questions in graph theory. Here a graph is a collection of vertices and connecting edges. Use (graphing-functions) instead if your question is about graphing or plotting functions.

0
votes
1answer
15 views

Partition pairs of numbers such that no partition contain two pairs with the same number.

Problem Integers $1, 2, 3, ..., n$ can form $\binom{n}{2}$ pairs of numbers. I want to partition these pairs of numbers such that: The number of partition is as low as possible None of the ...
0
votes
0answers
20 views

Laplacian Matrix

Hi I was reading about the Laplacian Matrix and I was encounter with this subject I would like to know why this is true:
0
votes
0answers
22 views

Zig Zag Product's Inequality [duplicate]

Hi I read this paper about the Zig Zag Product's (page 73 and 74) http://www.cs.huji.ac.il/~nati/PAPERS/expander_survey.pdf and I encounter this equation (page 74 top). and also this equation (page ...
-1
votes
0answers
44 views

Zig Zag Product's Problem

Hi I read this paper about the Zig Zag Product's (page 73 and 74) http://www.cs.huji.ac.il/~nati/PAPERS/expander_survey.pdf and I encounter this equation (page 74 top). and also this equation (page ...
0
votes
1answer
24 views

Zig Zag Product's Equation

Hi I read this paper about the Zig Zag Product's (page 73 below) http://www.cs.huji.ac.il/~nati/PAPERS/expander_survey.pdf and I encounter this equation. but I did not understand why this is true.
1
vote
1answer
21 views

Zig Zag Product's

Hi I read this paper about the Zig Zag Product's (page 73-74) http://www.cs.huji.ac.il/~nati/PAPERS/expander_survey.pdf and I encounter this equation. but I did not understand why this is true.
0
votes
0answers
7 views

How to combine multiple small connectivity matrices into one?

I have two connectivity matrices m1 and m2 of nodes 1 and 2 respectively. m1 = [0 50 3 20 4 30] m2 = [1 20 6 10] In each matrix, the ...
1
vote
0answers
16 views

Prove that for $k \geq 4$, a graph with $k$ vertices can have exactly 2 edge-disjoint minimum spanning trees

Prove that for $k \geq 4$, a graph with $k$ vertices can have exactly 2 edge-disjoint minimum spanning trees. I can define a graph as I wish, but it must hold that for $k\geq 4$, there are two min-...
0
votes
1answer
9 views

Proof of property of spanning trees

I am looking at a proof of the following property: "If graph T had order n, T is a tree if and only if it contains no cycles, and has n-1 edges." The proof of <= is as follows: Suppose T is a ...
4
votes
1answer
25 views

Partition a square with convex polygons. What is the maximal number of edges?

Given a square that is partitioned into convex polygons such that $n$ regions are created. What is the maxmimal number of edges in such a partition? Example. The two squares below both have $n=4$ ...
2
votes
1answer
10 views

why $e=e_2+v_i^2+\sum_{j=0}^{\sigma(G)}(i-j)\beta_{ij}(p)$

I need help with this problem: DEF: Let G be a $(3,l)$-graph. We let $v_i=l−1−i$, and we define $s_i$ to be the number of vertices of G of degree $v_i$. Let $G$ be a graph and $p$ a point of $G$. By ...
0
votes
0answers
15 views

Prim's algorithm loop invariant

Given an undirected graph G. At every step of Prim's algorithm, is the tree constructed so far an MST of nodes covered by Prim's? Can we prove this by contradiction or something? Or is there a ...
-1
votes
0answers
27 views

total number of spanning trees in a connected graph

Suggest a method for determining the total number of spanning tree in a connected graph without listing them.
0
votes
1answer
20 views

Can you construct a graph if you are given all its spanning trees?

Can you construct a graph if you are given all it's spanning trees? How?
1
vote
0answers
12 views

Is line graph $ L(C_n) $ of cycle graph $ C_n $ isomorphic to $ C_n $ itself?

I guess the answer is true. How can it be proved if it is true?
0
votes
0answers
16 views

Dimensionality of a Graph

In the past I have used stochastic cellular automata to evaluate chemical systems, with a 2D grid where each state corresponds to a chemical entity, the transitions are defined by certain chemical ...
0
votes
1answer
26 views

Why do the inequalities for planar graphs apply only if it is simple?

For planar, simple, connected graphs, with v≥3, we have e≤3v-6. If the length of the smallest circuit is 4, e≤2v-4. etc The proof of the inequalities is based on Euler's Formula which relies only on ...
1
vote
1answer
42 views

Theorem: $e_2\leq (y-1)[\frac{n}{2}-y+1+i]$

Help with this proof: DEF: Let G be a $(3,l)$-graph. We let $v_i=l−1−i$, and we define $s_i$ to be the number of vertices of G of degree $v_i$. Let $G$ be a graph and $p$ a point of $G$. By $H_1$ we ...
0
votes
0answers
36 views

Which bipartite simple graphs have a bipartite complement?

Suppose graph G is a simple graph. How many ways can this simple graph G be bipartite, and its complement be bipartite? Let k represent the vertices of graph G. Please list all the positive k ...
0
votes
1answer
31 views

Reflexive graph, meaning of the reflection

Here on the page 1 there is a definition of reflexive graph. I need an intuition how it works the morphism $e:X_0\to X_1.$ What is it and to what edge in $X_1$ it sends a vertex from $X_0$?
0
votes
0answers
29 views

Packing vertices on a hypercube graph?

Imagine a graph where the vertices and edges model an n dimensional hypercube (a line, a square, a cube and so on). A red vertex must have a minimum distance of 3 from every other red vertex. The ...
1
vote
1answer
37 views

Graph Theory - Discrete math

Can someone explain how to solve or start with this challenging equation? I have come to one conclusion which is to try the pigeonhole principle but can't get it right. Harry, being ahead of a ...
0
votes
1answer
14 views

Proving that if $\delta(G)=\min\limits_{v\in V}d(v)$, there exists a path of length $\delta(G)$: confusion about construction of path using neighbors

In a proof of this statement at some point we say that given $v_0v_1\dots v_k$, a path of maximum length, we can suppose that all neighbors of $v_0$ are in the path. I see how we can add one neighbor ...
2
votes
1answer
30 views

G is k-connected, then there is a cycle in G containing all $x_i$.

Let $G$ be a $k$-connected graph $(k ≥ 2)$, and let $x_1,x_2,...,x_k$ be vertices of $G$. Show that there is a cycle in $G$ containing all the $x_i$. First, Assum that $G$ is $k$-connected graph $(k ≥...
0
votes
0answers
32 views

Predict a subset from sequence of sets [on hold]

I want to solve this data mining problem: There are a sequence $S(t) = [A_1,...,A_{t-1}]$ . Each $A_i \subset U$ are set. Current time is $t \in \mathbb{N}$. $B$ is a subset of $A_t$. ($B \subset A_t$...
2
votes
1answer
28 views

What is the term for a graph in which each edge belongs to a Hamiltonian cycle?

Furthermore, are they any known results about these graphs, such as necessary or sufficient conditions for a graph to have this property?
1
vote
1answer
38 views

If a graph has less then $2n$ vertices, then it can't have $n$ spanning trees such that each pair is edge disjoint

If a graph has less then $2n$ vertices, then it can't have $n$ spanning trees such that each pair is edge disjoint This must apply for $n\geq 3$ I am not sure how to prove this. Probably the best ...
1
vote
2answers
27 views

Help on a graph theory question

Suppose G is an $n$-vertex graph containing no triangle as a subgraph. What is the best upperbound you can find for $d(u) + d(v)$, where u and v are two different vertices of $G$. (recall: $d(u)$ ...
1
vote
1answer
27 views

Problem on graphs with more edge than a Turan number

I ran into the following problem when revising for a Graph Theory exam - I had already solved part c) however I am keeping it in as it seems to link to part d). Now I see these type of problems on ...
1
vote
1answer
24 views

Can someone check my proof for: If a tree T has maximum degree k, then it has at least k leaves.

I have seen some proofs on this website for this problem using degree counting, but I was wondering if we could use induction? My proof is as follows: Base Case: $n = 2$ vertices Here, the number of ...
1
vote
1answer
31 views

Connected planar graph with $n \geq 4$ vertices and $m$ edges, all edges in a cycle and no 2 3-cycles share an edge: show $m \leq \frac{12}{5}(n-2)$

This was a question I came across whilst revising for a graph theory exam. I cannot see a way to begin tackling this problem. Thus far I have tried to go along the lines of the proof for the general ...
1
vote
1answer
20 views

Distance metric on vector space associated with edges of an undirected graph

Let $G = (V, E)$ be some graph representing for example, a physical road network. Intuitively, I can imagine that I can associate a distance between any two edges $e_1$ and $e_2$, $d(e_1, e_2)$, which ...
1
vote
1answer
49 views

I need a big regular polytope!

I have an ingenious project in mind that requires me to begin with a “big” graph of a regular polytope (# of vertices >, say, 50? 100?). This polytope can be of any dimension (I won’t be building it ...
1
vote
0answers
25 views

How to find the shortest path that pass through a group of Sets?

I have an algorithmic problem where I have a number of Unordered Sets of elements, and I need to find the shortest path (Ordered combination of the sets) that pass through all of those sets. There may ...
1
vote
2answers
45 views

proving that graph G is a path

I want to prove that the connected graph $G$ with $\delta(G) = 1$ and each vertex has a degree of $1$ or $2$, is a path. Can you tell whether my proof is correct? Since $G$ is connected, there is a ...
0
votes
0answers
21 views

The probability of seeing a vertex $v_j$ in less than $K$ steps from another vertex $v_i$

I want to calculate the probability of seeing vertex $v_j$ in a random walk in less than $K$ steps from vertex $v_i$ for every pair of vertices. Is there any approach for this problem in polynomial ...
2
votes
1answer
32 views

Embedding Dimension of a graph

Given a graph $G = (V, E)$, let the embedding dimension of a graph be the least number $n$ such that there exists a partitioning of $\mathbb{R}^n$ with the contact graph is $G$. Is there any way to ...
1
vote
1answer
21 views

Operation with graphs

I´m trying to apply the Euler theorem (V+F=E+2 on plane graphs) for a concrete graph (the following one). Thing is that I can use to operations: 1) Delete a node of grade 2 (that is, 2 edges on it) 2)...
0
votes
0answers
89 views

For which positive integers k can a simple graph G = (V, E) be constructed such that G is bipartite and its complement is bipartite? [on hold]

For which positive integers k can a simple graph G = (V, E) be constructed such that: G has k vertexes, that is, |V| = k, G is bipartite, and its complement G is bipartite? Supply a proof to prove ...
-1
votes
0answers
15 views

Distinct minimum spanning tree

For a connected, weighed, undirected graph G: G has a unique MST, if for every cut of G there is a unique minimum weight edge crossing the cut. Is this statement true? I think false because for the ...
1
vote
1answer
54 views

Suppose the edges of a complete graph of $10 $ vertices are coloured each either blue or red. Show that there is a blue triangle or a red tetrahedron

Could I get any help with this one, I'm lost. We know that the Ramsey number $R(3, 3)$ equals $6$. Suppose the edges of a complete graph of $10$ vertices are coloured each either blue or red. Show ...
0
votes
0answers
7 views

polynomial relations of $\operatorname{Hom}(\mathcal{A}^{\sigma}, \mathbb{R})$ in flag algebras

This question is about Razborov's 2007 paper on flag algebras. Under Definition 5, he introduces these positive homomorphisms in the set $\operatorname{Hom}^{+}(\mathcal{A}^{\sigma}, \mathbb{R})$. ...
0
votes
1answer
34 views

Spectral analysis

Prove that graph with the largest eigenvalue less than $2$ is acyclic. I tried to prove the above statement by taking into consideration the maximum degree. Maximum degree is greater than equal to ...
-1
votes
1answer
26 views

Proof in graph theory: maximum degree of a graph

I'm trying to solve this problem in graph theory: Prove that for every graph $G = (V, E)$ with $E \neq \varnothing $, it is true that: $$\Delta (G) \geq \left \lceil \frac{\left | E \right |}{\min\...
-2
votes
0answers
40 views

Does a graph exist with degree sequence (4, 3, 3, 1, 1) [on hold]

Does a graph exist with degree sequence (4, 3, 3, 1, 1) Simple graph; if not, why?
0
votes
0answers
21 views

How to sum over all allowed values of adjacency matrix?

I have troubles to understand the following simplification. $\sum_{\{A_{ij}\}} \Pi_{i<j} e^{\lambda A_{ij}} = \Pi_{i<j} \sum_{A_{ij =0,1}} e^{\lambda A_{ij}} $ How am I allowed to move the ...
1
vote
1answer
31 views

Notation for path in graph

Let $G=(V,E)$ be a graph with vertices $V$ and edges $E$. Is there standard notation for stating that $\pi$ is a path in $G$? I though about these options: $\pi \in G$ $\pi \sim G$ $\pi \in \text{...
0
votes
1answer
32 views

Minimal Spanning Tree With Algorithms

So I have a homework problem as above. The topic covered in class before this homework was Dynamic Programming. I have very little clue about what the question is actually asking: what is the MST ...
-1
votes
0answers
12 views

Proof for following question ? Prove that there will be a rectangle whose vertices all have the same color. [duplicate]

Suppose that all of the points of the plane with integer coordinates are colored red, blue, or green. Prove that there will be a rectangle whose vertices all have the same color.
0
votes
2answers
45 views

Graph Theory Questions With Connected Graphs [duplicate]

a. Four vertices are labeled $1,2,3,4$. In how many ways can edges be drawn between some pairs of these vertices so that the result is a connected graph? b. Five vertices are labeled $1,2,3,4,5$. In ...