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
29 views

Let $G$ be a $k$-regular bipartite graph, $k \ge 2$. Prove that every edge of $G$ appears in some perfect matcing in $G$. Is this proof correct?

Using Hall's Theorem, there could only be a perfect matching when the set of $|A|$ vertices have the same number of vertices as set $|B|$, and that there is a subset of vertices $|U|$ in $A$ that is ...
0
votes
1answer
18 views

In a directed graph with n≥2 nodes, if two different nodes reaches every nodes (including itself), then this graph is strongly connected.

I think this statement is true because if node a can reach every node (including node b) and node b can reach every node (including node a), there is an edge between node a and node b. This means that ...
0
votes
0answers
13 views

Algorithm for finding all maximum out-trees in a digraph

If we have a directed graph, and the graph contains subgraphs which are out-trees. We could find the set of out-trees, such that it does not contain any out-tree that is contained by another out-tree. ...
0
votes
2answers
47 views

Prove $G$ has at most $n^2$ edges.

If $G$ is a graph on $2n$ vertices that has exactly one perfect matching. My understanding is to add one more edge and then prove there are two perfect matchings, but it seems hard to prove ...
0
votes
0answers
10 views

Reducing a graph without lowering its chromatic number

While trying to find an algorithm to reduce a graph without lowering its chromatic number, I made the following algorithm (but not sure if it works): Given a (simple) graph $G$, look for subgraphs ...
4
votes
2answers
56 views

Why does the Number of Graphs on $n$ Vertices Blow up so Quickly?

See for example here: https://en.wikipedia.org/wiki/Graph_enumeration I would have thought (naively) that the number of graphs on $n$ vertices would only grow as $\mathscr{O}\left( _nC_2\right)$, but ...
0
votes
1answer
35 views

How to fill in the gaps in my proof to make it more convincing?

Let $T$ be a tree with $3$ edges. Let $G$ be a simple graph such that each vertex has degree at least $3$. Show that $G$ has $T$ as a subgraph. This statement is obvious but I am not sure how to ...
-1
votes
0answers
14 views

Vertex-cover-like problem with reduction to maximum flow

I am trying to solve the following problem: Solve the following problem by reducing it to the computation of a maximum s-t-flow: Let G be an undirected graph, $c:V\rightarrow\mathbb{Z}$ and ...
-1
votes
1answer
47 views

A graph G which can’t be painted properly in 2000 colors

A graph G which can’t be painted properly in 2000 colors (i.e. any two adjacent vertices have different colors) is given. The graph is properly painted in 2016 colors. Prove that a path of length 2000 ...
2
votes
0answers
42 views

In a directed graph with $n \geq 2$ nodes, if two different nodes reaches $n$ nodes, then this graph has a directed cycle.

I think this statement is true because if first node can reaches every other node (including second node) and second node can reaches every other nodes (including first node), then first node and ...
3
votes
1answer
25 views

Determine all maximal planar graphs, where one-third of their vertices have degree $3$, one-third have degree $4$, and one third have degree $5$.

To do this, I have $\frac {1}{3}n = \deg 3$, $\frac {1}{3}n = \deg 4$, and $\frac {1}{3}n = \deg 5$. I also know that $e=3n-6$ where $e$ is the number of edges and $n$ is the number of vertices. I ...
1
vote
1answer
27 views

Show every self-complementary graph on $4k + 1$ vertices has a vertex of degree $2k$.

I am not sure how to show this. I know a self complimentary graph on $4k+1$ vertices will have $\frac{\binom{4k+1}{2}}{2}=4k^2+k$ edges. I think another way to rephrase the problem is to show that ...
1
vote
1answer
31 views

What is a useful starting idea to think about this simple graph problem?

I would like to prove the statement that there are $2^{\binom{n-1}{2}}$ simple graphs are there with vertex set $\{1,\ldots,n\}$ such that every vertex has even degree. The thing that confuses me is ...
1
vote
1answer
13 views

How Many Marriages in a Bipartite Graphs?

Given two disjoint sets, say $M$ and $W$, both of size $n$, I want to compute how many possibilities of marriage exist. For example, when $n=1$, there are two marriages only: either $m_1-w_1$ or ...
12
votes
1answer
94 views

Why is the Topology of a Graph called a “Topology”?

The topology of a graph (i.e. a network topology), as far as I can tell, doesn't actually have anything to do with open or closed sets, nor does it have any consistent, rigorous definition in ...
0
votes
0answers
23 views

Maximum and Sets of vertex-disjoint paths in a not-directed graph

Let's consider a weighted graph $G = (V,E)$ not directed. In this graph, there are several sinks $S$, which are vertices. Let's consider one vertex $V$ of this graph (which is a source). The problem ...
1
vote
0answers
38 views

Running time of Edmonds-Karp algorithm

I have to prove that the running time of the Edmond-Karp-Algorithm is $\Theta({m^2}n$) by providing a family of graphs, where the Edmond-Karp-Algorithm has a running time of $\Omega({m^2}n$). I have ...
0
votes
1answer
19 views

Definition of vertex-cut for digraph?

I am trying to understand vertex cut for digraph. I could find this for graphs Vertex cut is a vertex whose removal increases the number of components in a graph. (D67, Handbook of Graph Theory by ...
0
votes
1answer
8 views

s-arc transitive graph is also (s-1)-arc transitive

I read on a paper that an s-arc transitive graph is also (s-1)-arc transitive and thus (s-2)-transitive, which was stated as obvious. However, I was thinking that a path of 2 edges, $P_2$, is 2-arc ...
2
votes
1answer
30 views

Definition of component for a digraph?

I could find this in Wikipedia Component: A connected component of a graph is a maximal connected subgraph. The term is also used for maximal subgraphs or subsets of a graph's vertices that have ...
4
votes
0answers
65 views

Central limit theorem for perfect matching counts

Set $N_G$ the number of copies of graph $G$ in the Erdős–Rényi random graph model $G(n,p)$. We have the law of large number for the number of copies of of graph $G$ i.e. $N_G$ is very close to the ...
1
vote
2answers
27 views

Shortest path in a graph with weighted edges and vertices

I am considering a problem of route planning (from a source $s$ to sink $t$) in a undirected graph with weighted edges and vertices. The goal is to find a shortest path between the source $s$ and the ...
1
vote
1answer
31 views

Is there a much easier way to find the vertices of a Eulerian Path?

If I have a $K_8$ graph like the one here and I want to label the Eulerian path for the vertices? what would be the best way to do this, there has to be a better way then just going through the lines ...
1
vote
0answers
36 views

Number of complex components with l=1 in G(n,p)

I need to prove that the number of specific components with complexity one, that is, two cycles connected by a path or an edge and one cycle with an inner path, on the set of vertices $\{1\ldots k\}$ ...
0
votes
2answers
21 views

Is it possible to have different solutions for isomorphic graphs?

According to the following graphs below, they are isomorphic. The matching pairs of the isomorphic graphs below are: a - 7 b - 3 c - 5 d - 4 e - 1 f - 2 g - 6 However, I have the following: ...
2
votes
1answer
48 views

Existence of trees in Erdos–Renyi random graphs $G(n, p)$

In Erdos–Renyi random graphs $G(n, p)$; Can someone give me the idea on how to prove that if $p\times n^{\frac{k}{k-1}}= o(1),$ then there is no tree of order $k$? The only hint that I can suppose ...
2
votes
1answer
58 views

On the number of some special components of a graph

In the book "Random Graphs" by Luczak; page 113, theorem 5.5, it's mentioned that if a graph $G$ contains a component with at least two cycles,$-$ the component must contain a sub-graph which either ...
-1
votes
0answers
32 views

Circles in k-connected graph

Can somebody help me with this question: Does there exist a $k \geq 4$ such that for every $k$-connected graph $G$ there is a set of its vertices $v_1,v_2...v_k$ for which there exists a circle that ...
0
votes
0answers
16 views

Finding maximum flow using Ford-Fulkerson on an undirected graph?

EDIT2: I just realized that you do indeed write 4/0 as the various paths connect up correctly anyway. It's difficult to wrap my head around but it does work itself out in the end. I will leave this ...
2
votes
1answer
44 views

What is the maximum number of cycles there can be in a graph with $x$ edges

Given a graph with $x$ edges and some number of vertices, what is the maximum number of cycles such a graph could possibly have? Here is an example of what I mean: Say you have 5 edges, then the ...
0
votes
1answer
18 views

Do lower order terms matter in Big Omega

Consider the function $(n-1)^2.$ Clearly this is $\mathcal{O}(n^2)$ since the constant for the upper bound is $1.$ However, it seems to me that it is not $\Omega (n^2)$ since this is a strictly ...
0
votes
0answers
19 views

Equivalent complexity of graph algorithms

Given a directed graph G = (V,E) with edge weights c: E -> R and r $\in$ V i have to show that the following 3 problems are equivalent: 1) Find a branching with maximum weight 2) Find a spanning ...
3
votes
2answers
47 views

When can you win this directed graph game?

I am trying to consider the conditions under which you can win the following directed graph game: Directed graph game: At the start of the game, you are given a directed, acyclic graph $G$ with ...
0
votes
0answers
7 views

Normalization of the log-Betweenness Centrality

In the paper I'm reading, the author refers to the betweenness centrality of a node with respect to another node, X. They then go on to define the 'node performance' as the normalized value of the ...
1
vote
1answer
16 views

Every almost $r$-regular graph has a spanning almost $(r-1)$-regular subgraph

Definition. A Graph is almost $r$-regular if each vertex has degree $r-1$ or $r$. Theorem. Let $G$ be almost $r$-regular for $r\geq 2$, then $G$ contains an almost $(r-1)$-regular graph $H$ with ...
0
votes
1answer
19 views

$G$ connected, $d(u)+d(v)\geq k$ for $u,v$ non-adjacent, then $\exists$ path of length $k$

Theorem. Let $k$ and $n$ be integers with $1\leq k<n$. Every connected graph of order $n$, in which $d(u)+d(v)\geq k$ for every pair $u,v$ of non-adjacent vertices, contains a path of length $k$. ...
1
vote
1answer
31 views

Let T be a spanning tree of a connected graph G..

Let $T$ be a spaning tree of a connected graph $G$ and let $e$ be an edge of $G$ not in $T$.Show that $T+e$ contains a unique cycle. So we know that if $T$ is spanning tree $\rightarrow$ $T$ is ...
0
votes
0answers
27 views

Cycle rank of a null graph

For the null graph N5, would the cycle rank be negative, since you have to add 4 edges for the graph to become a tree?
1
vote
0answers
21 views

What does a rooted forest look like?

I have heard the term rooted forest used in graph theory (I can't seem to find a good source to link, though). It seems like it is a collection of subgraphs of a directed acyclic graph, with each ...
-3
votes
1answer
37 views

Let $G$ be a graph with order $n$ prove that the chromatic number of $G \leq n$

Let $G$ be a graph with order $n$. Prove that the chromatic number of $G \le n$.
0
votes
0answers
15 views

Prove that the converse of a strong digraph is also strong

I would like to know how I prove this. The converse of a digraph D is obtained from D by reversing the direction of every arc of D. Show that a digraph D is strong if and only if its converse is ...
4
votes
1answer
473 views

The diameter of a specific 3-regular graph

On my HW assignment we were asked to prove the following claim: Let $G=(V,E)$ be a $3$-regular graph, and $m$ a natural number so that $n=|V|\geq 3(2^m)-1$. Prove that the diameter of $G \geq ...
0
votes
1answer
17 views

A directed graph is acyclic iff the weight matrix of the graph is nilpotent.

I want to prove the above statement. Firstly, I saw many times the following statement: "A DAG is acyclic iff the adjacency matrix is nilpotent" but I cannot find anywhere this proof. I tried to ...
1
vote
1answer
34 views

For every pair $n,d$ such that $d \ge (n-1)/2$ prove that $G$ on $n$ vertices with minimum degree $d$ is edge d-connected.

For every pair $n,d$ such that $d \ge (n-1)/2$ prove that $G$ on $n$ vertices with minimum degree $d$ is edge d-connected. None of my observations I was able to obtain seem to be useful. I am just ...
0
votes
1answer
32 views

Is there a classification for this kind of graph?

Is there a classification for a graph with the following properties? Finite. Directed. Every vertex points to some vertex. The third property necessitates the existence of at least one cycle. All ...
-1
votes
1answer
18 views

Can you rearrange the vertices of a simple graph to determine if it is planar? [closed]

enter image description here enter image description here
0
votes
0answers
17 views

n-critical graph with order n+2

Problem: Let G be an $n$-critical graph of order $n+2$. Show that $\overline{G}$ consists of $C_5$ and some isolated vertices. What I've managed to do: Not much, since I don't have many tools at my ...
1
vote
1answer
45 views

Vertex connectivity of $K_n$ upon removal of edges of subgraph $C_n$

Consider graph $G$ = $K_n$ - $E(C_n)$ ($G$ is complete graph on $n$ vertices upon removal of edges of subgraph $C_n$). For every $n \ge 3$ find maximum $k$ such that $G$ is vertex $k$-connected. I ...
0
votes
0answers
21 views

Ore's “Graphs and Their Uses” Problem Set 1.5, Problem 2 …

Ore's classic book asks for a proof of the following. Is my proof correct? Show how each of four neighbors can connect his house with the other three houses by paths which do not cross (this is ...
1
vote
1answer
59 views

Chess King Tour 8x8 problem

Two squares on a chessboard are said to be neighbours if they have an edge or a corner on the board in common. This means that squares on the edge have 5 neighbours, on the corner have 3 neigbours, ...