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
2answers
42 views

Does there exist a big graph with that property?

Does there exist a graph with the chromatic number greater than $2013$ and all the cycles of length greater than $2013 $ too?
1
vote
1answer
37 views

Relationship between graph edge count and coverability

Let $G$ be a connected graph on $n$ nodes, $m$ edges. A graph is $(b, r)$ coverable if it can be covered by $b$ balls of radius $r$ (in other words, there is a set of $b$ nodes such that all nodes ...
1
vote
1answer
78 views

Rank-one modification of graph Laplacian

Suppose I have a Laplacain matrix for a 3-node-path graph as follows $L=\left[\begin{array}{ccc} 1 & -1 & 0\\ -1 & 2 & -1\\ 0 & -1 & 1 \end{array}\right]$ Now, I want to ...
0
votes
1answer
72 views

Degree sequence in $O(n)$

How can we determine the whether a sequence of non negative integers is a valid degree sequence in $O(n)$. I have determined an $O(n\log n)$ algorithm using erdos-gallai theorem.
6
votes
1answer
343 views

Spectral gap of mixture of Markov chains

Context Let $P$ be the transition matrix of an irreducible, aperiodic, discrete-time Markov chain. The spectral gap is given by $$\xi = 1 - \lambda_\max$$ where $\lambda_\max = \max\{\lambda_2, -\...
12
votes
3answers
736 views

Can there exist an uncountable planar graph?

I'm currently revising a course on graph theory that I took earlier this year. While thinking about planar graphs, I noticed that a finite planar graph corresponds to a (finite) polygonisation of the ...
2
votes
1answer
280 views

Graph theory: possible paths costs values between two vertices

G is an oriented weighted graph. Branch weights are called costs. A path is a sequence of edges which connects a sequence of vertices. A path length is the number of edges involved in this path. The ...
0
votes
1answer
36 views

How to describe symmetric nodes in a graph

For instance, in the path graph $P_4$, node $1$ and $4$ are symmetric, how to mathematically describe this in graph theory? And any algebraic properties related to this? Thanks!
1
vote
0answers
62 views

Number of nodes with degree d in a graph

Why the number of nodes with degree $d$ in a graph $G$ is equal to the number of copies of $d$-stars in $G$ that are not part of any $(d + 1)$ star in $G$ ? Isn't it possible to have nodes with ...
0
votes
1answer
68 views

Show that there is a tree with a certain degree sequence

Given a list of $p$ non-negative integers such that $\sum_{i=1}^{p}n_{i}=p$ and $\sum_{i=1}^{p}in_{i}=2p-2$ Show that there is a tree with $p$ vertices s.t. the degree of $n_{i}$ is $i$ for all $i$ ...
1
vote
1answer
333 views

Permutation matrix and simple directed graph

I have some code that works with simple directed graphs, but it is kinda slow. So I converted it to use an adjacency matrix instead of keeping a list of pairs of nodes. The code finds the ...
2
votes
1answer
453 views

The properties of graph and its relation with the largest eigenvalue

When I was solving questions from a graph theory book by Bondy and Murty, I came across this problem: ( Note: $\Delta$ represents the maximum degree. ) Show that: a) no eigenvalue of a graph ...
0
votes
2answers
90 views

Question on trees and leaves

Let $T$ be a tree and $S$ the set of vertices in $T$ with degree at least 3. Prove that the number of leaves in $T$ is: $$2+\sum\limits_{v\in S} (deg(v)-2).$$ I ran into this example in my text and it ...
2
votes
2answers
1k views

A connected graph in which each vertex has even degree is bridgeless

I know how to prove it when the degree of all vertices is 2. For larger even numbers i don't know if my proof works. Here is my proof by contradiction: Assume we have G = (V,E) with d(v) = 2 for all ...
2
votes
1answer
46 views

Show that $K_n \boxtimes K_n = K_{n^2}$, where $K_n$ is a complete graph of $n$th order.

Show that $K_n \boxtimes K_n = K_{n^2}$. I thought that I could show that the number of vertices are the same, i.e. $$|V(K_{n^2})| = |V(K_n \boxtimes K_n)|$$ and since it is a complete graph, it ...
0
votes
2answers
209 views

How many edges would I need to add to $K_{n,m}$ to make it complete?

How many edges would I need to add to $K_{n,m}$ to make it complete (instead of bipartite)? $(n,m \to n+m)$ I know that $K_n$ has $\frac{n(n-1)}{2}$ edges and $K_{n,m}$ has $nm$ edges, but I can't ...
1
vote
3answers
128 views

How to show that if $G$ is a graph with $\delta (G) \geq 2$ then $G$ contains a cycle?

I know a cycle is a closed trail with no repeated vertices except the first and the last (starts and ends at the same vertex). But I'm not sure how to go about proving this
1
vote
1answer
68 views

How to prove this graph theory question?

"An Eulerian tour is a walk that goes over every edge exactly once. If G is a graph on n vertices such that degree of each vertex is even then prove that G has an Eulerian tour." I'm thinking since ...
2
votes
2answers
90 views

What does this mean? $K_n \boxtimes K_n$

I have to show that $K_n \boxtimes K_n = K_{n^2}$. Where $K_n$ is a complete graph. What does the operator "$\boxtimes$" do?
1
vote
2answers
262 views

Graceful Labeling for cycle

This result has been proved by Rosa, but I can't find a link to see his paper. I want to show that the graph $C_n$ is graceful if and only if $n=4k$ or $n=4k-1$ for some integer $k$. It's not hard to ...
0
votes
1answer
71 views

Determine line crossing corner of cuboid and POV of a camera faced towards it, based on the angles in the photo

Say you were to take a picture to a corner of a room with 90 degree angled walls and ceiling. In that picture you'd see three radial lines (the edges of the walls) starting in the same point (the ...
1
vote
0answers
81 views

Prove that the minimum of row sums of a nonnegative symmetric matrix is preserved

Let $A$ be an $n\times n$ adjacency (nonnegative, irreducible and symmetric) matrix with zeros on the diagonal. Denote $i$-th row sum of $A^k$ as $r^{(k)}_i$, where $k\geq1$. I want to prove that if $...
0
votes
1answer
42 views

How I can prove the one order homology of a tree is zero

When T is a tree and d1 is boundary operator fromC_1(T) to C_0(T) how to prove kernel of d1 is {0} I think acyclic is key point but i don't know next step.
4
votes
2answers
151 views

How can I prove that the Wiener index of the hypercube graph is $k \cdot 4^{k-1}$?

I'm trying to find the Wiener index of the Hypercube graph, $Q_k$. In case anyone does not know what that is, it's a graph where every vertex is labelled by a binary $k$-tuple, and where two vertices ...
0
votes
2answers
43 views

Is it true that if a graph is $3$-connected, then it is $3$-edge-connected?

In order for a graph to be $3$-connected, it is not disconnected after one of its vertices of degree $3$ is removed. I tried to find the contradiction of that statement by counterexample, but I ...
1
vote
0answers
81 views

Algorithmically constructing graphs with specified degrees

In graph theory books there are lots of problems similar to these: Construct a graph of 7 vertices with exactly 5, 2, 1, 1, 1, 1, 1 degrees Prove or disprove that there is graph of 4 vertices with ...
3
votes
2answers
148 views

How many vertices does this tree have?

Suppose that $T$ is a tree. It has $e$ edges and $n$ vertices, and $\overline{T}$ has $10e$ edges. What is n? I think $n = 1$ is a solution, because $T$ can have no edges then, so $0=10*0$. A ...
2
votes
2answers
389 views

Winning a restricted game of Nim?

Given the following piles, find the Grundy number of the initial position and make the first move in a winning strategy given that no more than two sticks may be removed from a pile at any time. Pile ...
2
votes
4answers
576 views

Is a directed graph uniquely determined by the in/out degree of each node?

I never really thought of this problem. If we have two directed graphs $A$ and $B$ with the same set of nodes $V$, and we know that the in/out degree of each node is the same in the $A$ and $B$, is it ...
6
votes
2answers
1k views

Is there a relation that is irreflexive, anti-symmetric and not transitive?

from the set $\{a, b, c, d\}$? Of the one's I have tried, it at best is two of the three, but never all.
1
vote
1answer
132 views

Determining Grundy Numbers for an inverted takeaway game

Given the following game, I need to determine a winning strategy and find the set of positions in the kernel. I figure the best way to do so would be with Grundy numbers. Rules: The game consists ...
1
vote
2answers
2k views

Graph theory: If a graph contains a closed walk of odd length, then it contains a cycle of odd length

I am trying to prove what's on the title. I have been working on it for some time already and the problem I have is that I can't seem to prove that the cycle I get at the end is of odd length. Here ...
0
votes
1answer
43 views

Graph theorem(homework) [duplicate]

This is the theorem If $G$ is a graph, there are at least $2$ vertices(points ) always have the same degree. e.g: I have graph $G$, $(U,V)$ ,$4$ vertices $(e1,e2,e3,e4)$ ,and $4$ edges. So the ...
0
votes
1answer
31 views

Necessary and sufficient condition for a set of graphs to be hereditary

Let $\Gamma$ be the set all non-directed loopless graphs without multiple edges. A set $X$ of graphs is called hereditary if each induced subgraph of a graph in $X$ also belongs to $X$. If $M\...
0
votes
2answers
143 views

T and F on some discrete math concepts

I was studying and these questions came up on a review guide on the inter webs, but could was wondering if I was correct on them. 1.Let $B$ $\subset$ $A$ and $f$ : $B$ $\subset$ $A$ be a 1-1 and ...
1
vote
1answer
50 views

Number of edges in a digraph?

I know this might be similar to this question, but I would like to know what the maximum number of edges in a digraph would be if parallel edges (aka multi-edges) are not allowed. I know that the ...
3
votes
1answer
91 views

existence of spanning trees in complete graphs implies choice?

it is known that the existence of spanning trees in arbitrary (connected) graphs implies the Axiom of Choice. I was wondering if this result still holds if we restrict ourselves to spanning trees of ...
1
vote
1answer
81 views

If a graph contains $3$ blocks and $k$ cut vertices, what are the possible values of $k$?

Since blocks can intersect in at most one articulation point, There are from 0 to 3 cut vertices. This is what I have so far. I'm not sure if I need to expand on this or if it is enough of an ...
1
vote
0answers
89 views

A question regarding a prefix code

Let $C=\{ c_1, c_2, \dots, c_m \}$ be a set of sequences over an alphabet $\Sigma$ and $|\Sigma|=\sigma$. Assume that $C$ is a prefix-free code, in the sense that no codeword in $C$ is a prefix of ...
2
votes
1answer
50 views

Prove that if $G$ is a graph of order $n \geq 3$ such that $deg$ $v \geq \frac{n}{2}$ for every vertex $v$ of $G$, then $G$ is nonseparable

I know a nonseparable graph is a connected graph with simply no cut vertices. And that a graph of order at least $3$ is nonseperable if and only if every two vertices lie on a common cycle. I'm not ...
3
votes
2answers
121 views

What is the average pathlength and probability to cross any given graph?

To get specific first off, it's about this graph: I want to get from $A$ to $B$. Every edge has the same length (e. g. 1 m). The shortest walk from $A$ to $B$ is easily found ($A-2-5-B$ and $A-3-6-...
4
votes
2answers
917 views

Given two non-isomorphic graphs with the same number of edges, vertices and degree, what is the most efficient way of proving they are not isomorphic?

After being given the following two graphs with the same number of edges, vertices and degree, I'm trying to show that they are not isomorphic. At least they seem to be non-isomorphic from the time I ...
1
vote
1answer
53 views

Graphs: Show that for $K_{17}$ there exist an edge coloring with 8 colors with a circle colored by one color.

Show that for $K_{17}$ there exist an edge coloring with 8 colors with a circle colored by one color. My work so far: We know that for each vertex, $v_i$, it's degree is $d(v_i)=16$, because the ...
1
vote
1answer
89 views

Question on Planar Graph

Let $\delta$ denotes the minimum degree of vertex in a graph. For all planar graphs on $n$ vertices with $\delta\geq3$, which of the following is TRUE? $i)$ In any planar embedding, the number of ...
2
votes
2answers
213 views

Proving a cut vertex in a tree, $T$, is an end-vertex:

If $T$ is a tree of order at least $3$, then $T$ contains a cut vertex $v$ such that every vertex adjacent to $v$, with at most one exception is an end vertex. I know that if $T$ is a connected graph ...
1
vote
1answer
193 views

Do subgraphs imply non-planarity if they correspond to subdivisions of K3,2 and K5 graphs?

I was given this problem: "Determine which of the graphs in figure 2 are planar. In each case either draw a planar graph or exhibit a subgraph which is a subdivision of K3,3 or K5". I did the first ...
3
votes
0answers
48 views

A stronger condition than planar graph?

Is there a name for this condition on a graph: a graph that can be embedded in the plane (planar), in such a way that of its univalent vertices do not lie inside any face? So, one can think of this ...
2
votes
1answer
78 views

The rational unit distance graph is bipartite

I am trying questions from a Graph theory book by Bondy and Murty. I stumbled across a neat looking problem. The unit distance graph on a subset $V$ of $\mathbb{R}^2$ is the graph with vertex set $...
0
votes
1answer
47 views

psittacism: Fundamental Theory of Time

This question is in reference to the programming question found here. What method of approach should I be thinking of if I have a list of lectures A, B, and C, and discussions D, E, and F, that are ...
1
vote
1answer
191 views

Find subgraphs in a directed graph which are isolated by edge properties

Please excuse my small knowledge of graph theory vocabulary. I can only describe the problem with common english words. Maybe someone can point me into the right direction and/or terms to look up. ...