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

0
votes
0answers
7 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
1 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
16 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
14 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
22 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
15 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
17 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
7 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
18 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
19 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. ...
2
votes
0answers
26 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 ...
0
votes
1answer
21 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
9 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
20 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
0answers
33 views

Induced H from G with given threshold

Definitions: 1) $G=(V,E)$ is undirected, weighted and simple (no edges between a node and itself and no parallel edges between two nodes). 2) $w(e)$ is the weight of $e\in E$ 3) $\forall ...
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
25 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
17 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
41 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
27 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
34 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
22 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
0answers
23 views

deleting edges in bipartite graph

Show that deleting at most $(m−s)(n−t)\over s$ edges from a $K_{m, n}$ will never destroy all its $K_{s, t}$ subgraphs. Any hints or proofs are greatly appreciated. I was thinking about using ...
1
vote
1answer
19 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 ...
0
votes
0answers
23 views

Evaluation a function of degree of vertices in a graph

I have a function $f(d)$ which takes in the degree of a vertex of a node in a graph $G$ and outputs a number between 0 and 1. The function is specified as follows. ...
0
votes
0answers
16 views

orbits/canonical labelling of colored graphs

Consider the following setting. We are given a simple undirected graph $G$ and a coloring $c:V(G) \mapsto \{0,1\}.$ We can compute the canonical labelling and $\rm{Aut}(G)$ efficiently. What I ...
1
vote
0answers
15 views

Combinatorial designs give triangulations of complete graphs

I recently attended a talk on combinatorial design theory. The speaker mentioned briefly that the Fano plane, and other designs give rise to triangulations of complete graphs (the Fano plane gives a ...
1
vote
1answer
58 views

Largest number of edges removed from $Q_{10}$ such that the graph always has a Hamiltonian cycle.

What is the largest number of edges that can be removed from $Q_{10}$ such that the graph always has a Hamiltonian cycle. Obviously it is $\leq 8$ as otherwise you can take $9$ edges away from one ...
0
votes
1answer
17 views

Coloring 4 by 3 square such that every unit square has an even number of squares it shares a vertex with of the same color (including itself).

Coloring 4 by 3 square such that every unit square has an even number of squares it shares a vertex with of the same color (including itself). I don't think this is possible, I have done a fair bit ...
1
vote
0answers
29 views

average degree inequality

Let $G$ be a graph with $|E(G)| ≥ 1$ and average degree $d(G)$. Prove that $G$ contains a subgraph $H$ with $δ(H) >{d(H)\over 2} ≥{d(G)\over 2}$. I'm not sure how to show that $δ(H) >{d(H)\over ...
-1
votes
0answers
12 views

if L(G) is a complete graph then F is a star - True or false [on hold]

Need help with this one if L(G) is a complete graph then F is a star - True or false
1
vote
1answer
29 views

3-connected graphs simple question

I have a relatively simple question. I was given this exercise A graph $G$ is called $2$–connected if for every pair of vertices $x$ and $y$ there are at least $3$ internally disjoint $xy$–paths in ...
0
votes
0answers
16 views

Special partitions for cubic 3-edge connected graphs

I'm trying to prove the following A cubic 3-edge connected graph $G = (V, E)$ allows partitions $T_{i}\subset E$ such that $G\setminus T_{i}$ is 2-edge connected, for $i = 1,\ldots, 5$. In ...
0
votes
2answers
24 views

Property of the numbering in preorder traversal of the tree

$v$ denotes the vertex which has been asigned the number $v$. The vertices are numbered in the order visited. In preorder all vertices in a subtree with root $r$ have numbers no less than $r$. More ...
0
votes
1answer
27 views

A cycle in an undirected graph

A cycle is a simple path of length at least $1$ which begins and ends at the same vertex. In an undirected graph, a cycle must be of length at least $3$. Could you explain me why that stands??
0
votes
0answers
29 views

Algorithm Generate all labeled graphs

I'm trying to find an algorithm which will generate all labeled graphs with $n$ nodes and $n-1$ edges. It must cover trees and graphs with cycles with one unconnected node, but without multigraphs. ...
0
votes
1answer
32 views

Maximum flow problem with both minimum and maximum capacities

I'm trying to develop an algorithm for a variant of the st-Maximum Flow problem where each edge has a maximum capacity $c_{max}$ and a minimum capacity $c_{min}$. The output should be a maximum ...
1
vote
2answers
47 views

Simple proof by contradiction in graph theory

The question is as follows: Let P be the longest path in a simple graph G, and let $\lambda$ be the length of P. Show that both the starting point and ending point of P must have degree $\le\lambda$. ...
0
votes
0answers
30 views

Proof that no Eulerian Tour exists for graph with even number of vertices and odd number of edges

How would you prove that for a connected graph with an even number of vertices and an odd number of edges, at least one of the vertices has an odd degree? My first attempt at solving this has been to ...
0
votes
0answers
10 views

What is a scale free network? [closed]

What I want to know is what scale is a 'scale-free network' free of? This is a the part I'm confused on.