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.

learn more… | top users | synonyms

1
vote
1answer
13 views

The circumference of a hypercube graph

How can I find the circumference of a hypercube graph? is easy to see that a n-dimensional hypercube have a $2n$-cycle, but I cant prove that it's the largest, can anybody help me?
0
votes
1answer
9 views

Every nonhamiltonian 2-connected graph has a theta subgraph

If a graph $G$ has a spanning cycle $Z$, then $G$ is called a Hamiltonian graph and $Z$ has a Hamiltonian cycle. A theta graph is a block with two nonadjacent vertices of degree 3 and all other points ...
5
votes
3answers
59 views

Secret Santa Perfect Loop problem

(n) people put their name in a hat. Each person picks a name out of the hat to buy a gift for. If a person picks out themselves they put the name back into the hat. If the last person can only ...
1
vote
1answer
23 views

Graph and one Sequence challenge

We have in and out degree of a directed graph G. if G does not includes loop (edge from one vertex to itself) and does not include multiple edge (from each vertex to another vertex at most one ...
1
vote
1answer
8 views

P - bounded polyhedron, L - linear map. Show that L(P) is a bounded polyhedron

Let $P = \{x\in \mathbb{R}^n \ | \ Ax\leq b\}$ be a bounded polyhedron. Let $L:\mathbb{R}^n \rightarrow \mathbb{R}^k$ be a linear map. Show that $L(P):=\{L(x)\ | \ x\in P\}$ is a bounded polyhedron. ...
0
votes
0answers
13 views

Is this a Red-Black Tree?

I tried to build RBT (Red-Black Tree) via this way: I build a balanced binary search tree (much as I can) and then colored it... Now the Q is: if this is a legal RBT? At my opinion is yes, because ...
3
votes
1answer
46 views

Graph with only the identity as endomorphism

Is there a graph $G$ with more than one vertex such that the identity $\textrm{id}: G\to G$ is the only graph homomorphism from $G$ to itself? Is there even an infinite example?
1
vote
1answer
16 views

Show that $\delta(G) \geq 4$ if $\chi(G)=5$ and $\chi(G-v) =4$ for each vertex $v \in G$

Let G be a graph satisfying the following conditions: (1) $\chi(G)=5$ and (2) $\chi(G-v) =4$ for each vertex $v \in G$ Show that $\delta(G) \geq 4$. Answer given: Suppose $\delta(G) \leq 3.$ Let ...
0
votes
0answers
9 views

Graph Minor/Subdivision Proof

Prove that if $G$ contains a $K_5$ or $K_{3, 3}$ minor, then $G$ contains a $K_5$ or $K_{3, 3}$ subdivision. Any proofs or hints are greatly appreciated.
0
votes
1answer
14 views

Does the maximum cut implies the minimum flow?

Is it possible to reverse the result of the min-cut max-flow theorem and obtain the result that if you have the maximum cut, then you have the minimum flow? I've been thinking about it, but I have no ...
0
votes
0answers
8 views

Upper bound for graphs with no k-cliques

We know that for random graphs $G(n,p)$ we have: $P[X=0]\leq e^{-\Theta(E[X])}$ where $X$ denotes the number of k-cliques in the random graph. Can this fact be used to say anything about the number of ...
0
votes
0answers
5 views

Algorithm for creating a directed scale free network with a fixed amount of nodes

I'm trying to figure out an algorithm that produces a scale free, directed network, for which I can give the final amount of nodes as an input. Now, this is a little bit tricky for a few reasons, so ...
0
votes
1answer
20 views

Number of possible graphs from a reachability matrix?

I need to know how to work out how many possible different digraphs can be drawn from a given reachability matrix. It needs to be with the minimum number of arcs between the nodes within the graph ...
1
vote
1answer
15 views

Power set ordered by sum and Dijkstra shortest path

I've needed to enumerate the power set ordered by the sum of elements in each subset. Luckily I've found a nice solution here: Algorithm wanted: Enumerate all subsets of a set in order of increasing ...
0
votes
1answer
14 views

Number of graphs with M edges that does not contain K-clique

If we consider the space of graphs $G(n,M)$ with $n$ vertices and $M$ denotes the number of edges. Is there any way of upper bounding the number of graphs in this space that does not contain any ...
0
votes
1answer
11 views

Proof between max independent set cardinal and min vertex cover.

i'm tryign to solve this problem for my graph class, but I don't really know where to start. Be G a graph without isolated vertex,proof that it verifies that $\alpha \leq \beta$, where $\alpha$ is ...
0
votes
1answer
10 views

Clarification on Eulirian cycle proof

I have trouble in understanding this proof can some one clarify the following elements: (1)Why does it follow that if T has maximum length, then $v_0=v_k$?(2)What does E represent?(3)What does E(T) ...
0
votes
0answers
11 views

what is the name or class of such graphs: the probability that two nodes are connected is decided a function of the distance

Random geometric graph is: Randomly place N nodes in a topologic space, if the distance between two nodes is smaller than a specific value, then these two nodes are connected. Now, slightly ...
0
votes
0answers
15 views

Example of a k-matroid

Let the set $K_i = (S, I_i)$ be a matroid for each $i \in \{1 \ldots k\}$. We define $K = (S, I) $ where $I = \{ X \subset S $ | $ X \in \bigcap_{i=1}^k I_i\}$ The claim now is that $K$ is a ...
0
votes
0answers
4 views

Recommendation needed in graph theory and statistics to be used in football predictions.

The following is a very simple model of what I am working on. I just need some advice since I don't have graph theory background. Suppose that A played at home against B and won by 3 goal ...
1
vote
1answer
35 views

Minimum number of edges to ensure connectedness

Question: Consider a simple graph G with n vertices. What is the minimum number of edges that G must have in order to ensure that it is connected? Justify your answer. My attempt: Let G = $(V, E)$. ...
0
votes
1answer
15 views

given a point cloud of n points, create a convex shape that defines their outer limits

I have a point cloud. I find its 'centre' by averaging the coordinates of each point. I translate the cloud so the average is at the origin (for simplicity sake) I want to then create a convex shape ...
1
vote
0answers
28 views

What is the multiplicity of the largest eigenvalue of a graph?

The Laplacian of a graph is a symmetric positive semi-definite matrix and hence has all real eigenvalues. Is there any characterization for the multiplicity of the largest Laplacian (and/or Adjacency ...
1
vote
1answer
22 views

how we can understand from spectrum of laplacian matrix of a graph that this graph is regular or not .

how we can understand from spectrum of laplacian matrix of a graph that this graph is regular or not . if we consider $0=\mu_1 \leq \mu_2 \leq ...\leq \mu_n$ as the eigenvalue of laplacian matrix ,we ...
0
votes
0answers
21 views

Coloring edges of $K_n$ so each vertex has $l$ edges of each color.

Given $n$ for what values of $l$ can we color the edges so that each vertex $l$ edges of each color adjacent to it. The number of colors used is clearly $\frac{n-1}{l}$ Thank you in advance.
1
vote
0answers
19 views

Is the product of (modified) adjacency matrices of two matchings necessarily symmetric?

Consider $n$ vertices, and two (not necessarily perfect) matchings $M_1$ and $M_2$. With the following definition of a (modified) adjacency matrix of a matching, can we claim that $A(M_1)\cdot A(M_2)$ ...
0
votes
0answers
8 views

For what values of $l$ is $K_n$ the disjoint union of $l$-regular graphs?

Given $n$ for what values of $l$ can we see $K_n$ as a disjoint union of $l$-regular graphs? By disjoing union I mean we don't add th same graph twice. Oh and the graphs don't need to be spanning. ...
0
votes
2answers
19 views

Assign integers to the vertices of $G$

Let $G=(V,E)$ be a directed acyclic graph. I have to write an algorithm to assign integers to the vertices of $G$ such that if there is a directed edge from vertex $i$ to vertex $j$, then $i$ is less ...
0
votes
1answer
21 views

Proving number of edges in F = n - k

So if we let F = (V,E) be a forest with n vertices and k connected components (trees), how can I prove that the number of edges in F = n - k ? I was thinking of using induction, but I'm super lost. ...
3
votes
1answer
50 views

Does a colouring of a graph on two colours always have certain kinda of circle

Is there a planar set of points $P$ $(|P|\geq 4)$ such that no matter how you colour the points with two colours you can always find four points on a circle so that all four of the point have the ...
1
vote
1answer
32 views

Can the complete graph $K_9$, be 2-coloured with no blue $K_4$ or red triangles? (Ramsey Theory)

I am working on the following problem on 2-coloured complete graphs: $K_9$ is coloured red and blue and contains no red triangle and no blue $K_4$ then every vertex must have red degree 3 and ...
1
vote
1answer
7 views

Prove that you cant you fill all spots in this grid.

We have a $4$ by $5$ grid with $A$ in the lower left corner, and $B$ in the middle of the left lane. Why can't you draw a line from $A$ to $B$ which goes through all the spots in the grid? This ...
1
vote
0answers
19 views

Prove that if there are $2n$ points and $n^2+1$ straight lines connecting them, then there are at least $n$ triangles in this shape.

Proof by induction. For $n=2$, it says that if we have $2(2)=4$ points and $2^2+1=5$ lines connecting them to each other, then there are at least 2 triangles in this shape. Which is true (shown ...
0
votes
1answer
10 views

Calculate edge probability of a graph

I wonder what is the edge probability $p$ for which a random graph with $n = 5000$ nodes has the largest expected diameter? How can I calculate that? Is there someone who can help me? This would be ...
0
votes
1answer
23 views

A small confusion in network flows (conservation constraints).

I'm reading the Handbook of Graph Theory. I guess It says that the sum of the flows going is equal do the sum of flows going back, I'm confused about what is the value of the flow going ...
1
vote
2answers
17 views

Proof of connectedness in a simple graph

Let G be a simple graph with n vertices. Prove that if the degree of every vertex is at least $\frac{n-1}2$, then G is connected. I've tried the degree sum formula, but it doesn't seem to get me ...
0
votes
1answer
16 views

Probability of edges in Graph

I have given a random graph G(n, p) with n = 5000 vertices and an edge probability of p = 0.004. I calculated the expected number of edges which is (0.004 * maximum number of possible edges) $pE = ...
0
votes
0answers
26 views

why Petersen graph has exactly six perfect matching? [on hold]

Must I find all six matching and show, that there cannot be more? I know, that all cubic graphs have at least 5 matching.
0
votes
1answer
25 views

Fundamental group of graphs

If $G$ is a connected graph with a maximal tree $T \subset G$ such that: $G-T$ consists of only a single edge $e$, then how would i find the fundamental group $\pi_1(G)$ and show that it ...
0
votes
0answers
29 views

How many first neighbors does a node whose degree is known in an undirected graph have?

Consider a graph $\mathcal{G} = \left(V,E\right)$ with vertices (nodes) $V$ and undirected connections between them $E$. If I know the degree of the $i$th node, $d\left(i\right) = k$, and the ...
1
vote
0answers
34 views

Example of a series parallel graph with toughness greater than $\frac{4}{7}$

Can anyone lead me to an example of a "more than $\frac{4}{7}$ tough series parallel graph"? Graph toughness is defined as $T = \min \left\{\frac{|a|}{\omega{(G\backslash A)}}\right\}$ over all ...
0
votes
1answer
18 views

quotient graph $G^R$

I understand that if $R$ is an equivalence relation on $G$, the resulting partition cells are either equal or disjoint. I think I understand that the graph of the quotient set $G^R$ is constructed ...
0
votes
1answer
42 views

What is $\Gamma(a)$?

I'm reading Van Lint's Course in Combinatorics: He mentions $\Gamma(a)$ in this text but I'm not really sure of what it means and I'm also afraid of assume something wrong, at first thought I ...
0
votes
0answers
28 views

What's the meaning of dual concept?

I've read the following on The Handbook of Graph Theory: 11.1.2 Minimum cuts and Duality An important and dual concept related to maximum flows is that of minimum cuts. I know that the value ...
0
votes
1answer
36 views

Proving a connected graph cannot have only even-degree vertices

I want to prove that a connected graph with m edges and n vertices must have at least one vertex of odd degree. In particular, I want to prove this for a graph of 53 edges and 11 vertices; but also in ...
0
votes
0answers
41 views

Finding spanning trees using Depth-First Search

I am wondering if root in spanning trees using Depth-First Search can have more than $2$ children? I know this is a silly question, but there is an example in the book which involves only $2$ ...
-1
votes
0answers
24 views

Is it true that a tree on n vertices has n-1 edges and graph has 2n edges? [on hold]

I'm a bit confused how can these two theorems exist at the same time. A tree on n vertices has n-1 edges but graph has 2n edges [Hand-Shaking Lemma]. I know Induction Proof for the first part but the ...
0
votes
1answer
35 views

Prove that every connected undirected graph with n vertices has at least n-1 edges.

I would appreciate it if anyone can verify my proof. It is a proof by induction, but I attempt to reason things out rather than using a purely mathematical approach, in a similar vein to many other ...
1
vote
0answers
23 views

Random walk return for subgraph

Assume that $G$ is a finite graph and we have a simple random walk starting at some vertex $v$ of $G$. We fix $n$, and consider the probability that the random walk does not return to $v$ after $n$ ...
1
vote
1answer
20 views

Connectivity of a Hamiltonian path

Show that if G has a Hamiltonian path then for every proper subset S of V, $\,$ $\omega(G-S)\leq\vert S \vert + 1$,$\,$where V is the set of the vertices of G and $\omega$ is the number of the ...